嗯...
题目链接：https://www.luogu.org/problemnew/show/P2661
这道题和一些比较水的并查集不太一样，这道题的思路就是用并查集来求最小环...
首先，如果我们把题目中的每一个同学都看成是一个点，并且信息只能由 i 给 T[i]，所以可以看成是一个有向图，并且当自己的信息别人告诉自己的时候，说明这个有向图已经成为了一个环了。而要求游戏可以进行几轮，就是要求最小环。
核心思想：
假如说信息由A传递给B，那么就连一条由A指向B的边，同时更新A的父节点，A到它的父节点的路径长也就是B到它的父节点的路径长+1。这样我们就建立好了一个图，之后信息传递的所有环节都按照这些路径。游戏结束的轮数，也就是这个图里最小环的长度。如果有两个点祖先节点相同，那么就可以构成一个环，长度为两个点到祖先节点长度之和+1，最后取min就好。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; int n, minn = 0x7f7f7f7f;
int f[], d[]; inline int find(int x){
if(f[x] !=x ){
int last = f[x];
f[x] = find(f[x]);
d[x] += d[last];
}
return f[x];
} inline void check(int a, int b){
int x = find(a), y = find(b);
if(x != y){
f[x] = y;
d[a] = d[b] + ;
}
else minn = min(minn, d[a] + d[b] + );
} int main(){
int t;
scanf("%d", &n);
for(int i = ; i <= n; i++) f[i] = i;
for(int i = ; i <= n; i++){
scanf("%d", &t);
check(i, t);
}
printf("%d", minn);
return ;
}
AC代码