https://www.luogu.com.cn/problem/P2661

题意 ：求有向图的最小环

tarjan : 求所有的强连通分量，再取最小值。
并查集：（别处看来的思路）把每个同学看成一个点，信息的传递就是在他们之间连有向边，游戏轮数就是求最小环。
图论求最小环，我在里面看到了并查集。
假如说信息由A传递给B，那么就连一条由A指向B的边，同时更新A的父节点，A到它的父节点的路径长也就是B到它的父节点的路径长+1。
这样我们就建立好了一个图，之后信息传递的所有环节都按照这些路径。游戏结束的轮数，也就是这个图里最小环的长度。
如果有两个点祖先节点相同，那么就可以构成一个环，长度为两个点到祖先节点长度之和+1。
topsort :经典的求圈…

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
const int INF=0x3f3f3f3f;
const int MAX=200000+10;
int Low[MAX],DFN[MAX],Stack[MAX],Belong[MAX];
int n,x;
int ind,top;
int scc;   //强连通分量的个数 
bool InStack[MAX];
int num[MAX];//各个强连通分量包含点的个数
vector <int> e[MAX]; //边表
void tarjan(int u,int fa){
	int v;
	Low[u]=DFN[u]=++ind;
	Stack[top++]=u;
	InStack[u]=true;
	int size=e[u].size();
	for(int i=0;i<size;i++){
		v=e[u][i];
		if(v==fa) continue; //
		if(!DFN[v]){
			tarjan(v,u);
			Low[u]=min(Low[u],Low[v]);
		}else if(InStack[v]){
			Low[u]=min(Low[u],DFN[v]);
		}
	}
	if(Low[u]==DFN[u]){
		scc++;
		do{
			v=Stack[--top];
			InStack[v]=false;
			Belong[v]=scc; //标记属于哪一个强连通分量
			num[scc]++;
		}while(v!=u);
	}
} 
void solve(int n){
	memset(DFN,0,sizeof(DFN));
	memset(InStack,false,sizeof(InStack));
	memset(num,0,sizeof(num));
	ind=scc=top=0;
	for(int i=1;i<=n;i++)
		if(!DFN[i])
			tarjan(i,-1);
}
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,1,n+1){
		sf(x);
		e[i].push_back(x);
		e[x].push_back(i);
	}
	solve(n);
	int _min=INF;
	fi(i,1,scc+1){
		if(num[i]!=1 && _min>num[i])
			_min=num[i];
	}
	pf(_min);
	return 0;
}

大佬的并查集代码

...