有 n 个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti? 的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？
输入格式：
共2行。
第1行包含1个正整数 n ，表示 n 个人。
第2行包含 n 个用空格隔开的正整数 T1,T2,....,Tn ，其中第 i个整数 Ti? 表示编号为 i 的同学的信息传递对象是编号为 Ti? 的同学， Ti?≤n 且Ti?≠i 。
输出格式：
1个整数，表示游戏一共可以进行多少轮。
5 2 4 2 3 1
规则是什么？
就是一个你的好朋友小飞会一直告诉你信息，然后你会把你的信息和小飞告诉你的信息一直告诉你的好兄弟小凯
然后当其中某个人知道他自己的信息时，游戏结束
其实，当我们理解了这个，就好分析问题了
因为信息传递的顺序是固定的，就是说小飞只会告诉你，而你也只会告诉小凯，这就让我们想到了用并查集
并查集就是 我们通常是在开始时让每个元素构成一个单元素的集合，
然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
“你告诉我，我告诉他”
如果说你能知道自己的信息，说明信息传了一圈又回来了
于是乎，我们就可以在并查集中求最小环得到答案
在代码中，我用了路径压缩，所以当我们求最小环时没法暴力跑出这个环经过哪几个点（因为路径压缩省略了中间过程）
怎么办呢，我用了f[]数组去记录每个点的下一个点是什么，比如f[小飞]=小凯
然后每次求出环的大小，记录一个最小的环（这个就不用多说了）
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int MAXN=200010; int t[MAXN]; int fa[MAXN]; int f[MAXN]; int ans,cnt; int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&t[i]); fa[i]=f[i]=i; } ans=2000010; for(int i=1;i<=n;i++){ int xx=find(i); int yy=find(t[i]); if(xx==yy){ cnt=1; for(int j=t[i];j!=i;j=f[j]){ cnt++; } ans=min(ans,cnt); } f[i]=t[i]; fa[xx]=yy; } cout<<ans<<endl; return 0; }
原文：https://www.cnblogs.com/xiaoK-778697828/p/9652579.html