Criska

Tarjan

• 分类: tarjan • 标签: tarjan

Tarjan很有用可是我今天才会写 → →，例题是noip2015 day1 第二题，Tarjan只能过80，所以我只是写篇博客记录一下Tarjan罢了，谢谢naive童鞋，我都是照抄他的%>_<%

1.noip2015 信息传递

题目描述

有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入输出格式

输入格式：

输入共2行。

第1行包含1个正整数n表示n个人。

第2行包含n个用空格隔开的正整数T1,T2,……,Tn其中第i个整数Ti示编号为i

的同学的信息传递对象是编号为Ti的同学，Ti≤n且Ti≠i

数据保证游戏一定会结束。

输出格式：

输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstdio>
#include<algorithm>
#define M 500000
using namespace std;
int n,tmp,tope,head[M],zotot,jiedian[M];
int dfn[M],low[M],tot;
int stk[M],isin[M],stktot;
struct node{
	int to,next,w;
}e[M];
int mi(int a,int b)
{
	if(a<b) return a;
	else return b;
}
int intt(int x,int y,int z)
{
	++tope;
	e[tope].to=y;
	e[tope].next=head[x];
	e[tope].w=z;
	head[x]=tope;
	
}
void tarjan(int x)
{
	dfn[x]=++tot;
	low[x]=tot;
	isin[x]=1;
	stk[++stktot]=x;
	for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
	{
		if(dfn[y]==0)
		{
			tarjan(y);
			low[x]=mi(low[x],low[y]);
		}
		else if(isin[y])
		{
			low[x]=mi(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x])
	{
		zotot++;
		for(int i;i!=x;)
		{
			i=stk[stktot--];
			jiedian[zotot]++;
			isin[i]=0;
		}
	}
}
int main()
{
//	freopen("message.in","r",stdin);
//	freopen("message.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&tmp);
        intt(i,tmp,1);
    }
    for(int i=1;i<=n;++i)
    {
        if(dfn[i]==0)
            tarjan(i);
    }
    sort(jiedian+1,jiedian+zotot+1);
    for(int i=1;i<=zotot;++i)
        if(jiedian[i]>1)
        {
            printf("%d",jiedian[i]);
            break;
        }
    return 0;
}

2.【洛谷1726】上白泽慧音

  • 坑爹题…………不知道输出的村庄为啥总不对(╯‵□′)╯︵┻━┻
    换了一个方法总算是过了……
    其实只是一个裸的tarjan加记录罢了

  • 好了认真学习过tarjan的我又回来解答我以上的疑惑了，要记得，根据如下的更新方式，一个强连通分量里的low[ ]值不一定是全部相等的！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,tope,head[N];
int dfn[N],low[N],in[N],stk[N],stktot,tot,tar[N],tartot,jilu[N],jie,ma=0;
struct node{
	int to,next;
}e[N];
inline int intt(int x,int y)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	head[x]=tope;
} 
inline int tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	in[x]=1;
	stk[++stktot]=x;
	for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
	{
		if(dfn[y]==0)
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else
			if(in[y])
			{
				low[x]=min(low[x],dfn[y]);
			}
	}
	if(low[x]==dfn[x])
	{
		tartot++;
		int i=0;
		while(i!=x)
		{
			i=stk[stktot--];
			jilu[i]=tartot;
			in[i]=0;
			tar[tartot]++;
		}
		if(tar[tartot]>ma)
		{
			ma=tar[tartot];
			jie=tartot;
		}
	}
	
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		intt(x,y);
		if(z==2) intt(y,x);
	}
	for(int i=1;i<=n;++i)
	{
		if(dfn[i]==0)
		{
			tarjan(i);
		}
	}
	printf("%d\n",ma);
	for(int i=1;i<=n;++i)
	{
		if(jilu[i]==jie)
			printf("%d ",i);
	}
	return 0;
}