信息传递

题目描述
有 n 个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti 的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入输出样例

输入
5
2 4 2 3 1

输出
3

题意很简单，如果信息可以传递回来，代表形成了一个环，所以题意就是要求找一个最小环。

看到这道题，有几种想法，可以用并查集找最小环，一直更新即可。另一种就是用 tarjan 找强连通分量，形成环，肯定构成一个强连通，那么直接 tarjan 找强连通大于 1 ，的最小强连通分量即可。

AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,dfn[N],low[N],vis[N],cnt,res=0x3f3f3f3f;
int head[N],nex[N],to[N],tot;
stack<int> st;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void tarjan(int x){
	dfn[x]=low[x]=++cnt;	st.push(x);	vis[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]);	low[x]=min(low[x],low[to[i]]);
		}
		else if(vis[to[i]])	low[x]=min(low[x],dfn[to[i]]);
	}
	if(low[x]==dfn[x]){
		int ans=0;
		while(1){
			ans++;	int u=st.top();	st.pop();	vis[u]=0;
			if(u==x)	break;
		}
		if(ans>1)	res=min(res,ans);
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;	cin>>x;	add(i,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])	tarjan(i);
	}
	cout<<res<<endl;
	return 0;
}