题目描述
有 nn 个同学（编号为 11 到 nn ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 ii 的同学的信息传递对象是编号为 T_iT
i
? 的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？
输入输出格式
输入格式：
共 22 行。
第 11 行包含1个正整数 nn ，表示 nn 个人。
第 22 行包含 nn 个用空格隔开的正整数 T_1,T_2,\cdots\cdots,T_nT
1
? ,T
2
? ,??,T
n
? ，其中第 ii 个整数 T_iT
i
? 表示编号为 ii 的同学的信息传递对象是编号为 T_iT
i
? 的同学， T_i \leq nT
i
? ≤n 且 T_i \neq iT
i
? ≠i 。
输出格式：
11 个整数，表示游戏一共可以进行多少轮。
输入输出样例
输入样例#1： 复制
5
2 4 2 3 1
第一种 Tarjan 强连通分量，取个最小就行了，（模板）这里就不贴了
第二种 ，并查集， 这个图的输入很特殊，每个点都有一个出边，所以如果在同一个集合中 ，那么这时候添边一定会产生一个环，这个时候我们再暴力回溯找环中点的个数。
注意在建立原图过程中，建立方向边，这样才可以让回溯找路径的时候 不会有歧义 而产生错误。
代码
#include <bits/stdc++.h>
using namespace std;const int N = (int) 200000 + 11;
const int M = (int) 5e5 + 11;
const int mod = (int) 1e9 + 7;
const int inf = 0x3f3f3f3f;int pre[N], fa[N], T[N];
void init(int n){for(int i = 0; i <= n; i++) {pre[i] = fa[i] = i;}
}int Find(int x){if(x == pre[x]) return x;else {return pre[x] = Find(pre[x]);}
}int main(){int n; scanf("%d", &n);init(n);for(int i = 1; i <= n; i++) scanf("%d", &T[i]);int ans = inf;for(int i = 1; i <= n; i++){int x = Find(i); int y = Find(T[i]);if(x == y){int cnt = 1;for(int j = T[i]; j != i; j = fa[j]) cnt++;ans = min(ans, cnt);}else {fa[i] = T[i]; // 原图中 建立方向边，这样才可以唯一确定路径pre[x] = y;}}printf("%d\n", ans);return 0;
}