并查集求最小环
https://www.luogu.org/problemnew/show/P2661
把每个同学看成一个点，信息的传递就是在他们之间连有向边，游戏轮数就是求最小环。假如说信息由A传递给B，那么就连一条由A指向B的边，同时更新A的父节点，A到它的父节点的路径长也就是B到它的父节点的路径长+1。
这样我们就建立好了一个图，之后信息传递的所有环节都按照这些路径。游戏结束的轮数，也就是这个图里最小环的长度。如果有两个点祖先节点相同，那么就可以构成一个环，长度为两个点到祖先节点长度之和+1。
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 2e5 + 5;
int f[maxn], dis[maxn], minn; // f保存祖先节点，dis保存到其祖先节点的路径长。
int n;int find(int x) {if (f[x] != x) { //查找时沿途更新祖先节点和路径长。int last = f[x]; //记录父节点（会在递归中被更新）f[x] = find(f[x]); //更新祖先节点。dis[x] += dis[last]; //更新路径长（原来连在父节点上）。}return f[x];
}
void check(int a, int b) {int x = find(a), y = find(b); //查找祖先节点。if (x != y) { //若不相连，则连接两点，更新父节点和路径长。f[x] = y;dis[a] = dis[b] + 1;} else { //若已连接，则更新最小环长度。minn = min(minn, dis[a] + dis[b] + 1);}
}int main() {// freopen("data.txt", "r", stdin);int a;cin >> n;minn = 0x3f3f3f3f;for (int i = 1; i <= n; i++) //祖先节点初始化为自己，路径长为0。f[i] = i;for (int i = 1; i <= n; i++) {cin >> a;check(i, a); //检查当前两点是否已有边相连接。}cout << minn;return 0;
}
来源 https://anyway.blog.luogu.org/solution-p2661