acwing 517. 信息传递

地址 

有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。

在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 TiTi 的同学。 

游戏开始时，每人都只知道自己的生日。

之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。

当有人从别人口中得知自己的生日时，游戏结束。

请问该游戏一共可以进行几轮？

输入格式
输入共 2 行。 

第 1 行包含 1 个正整数 n ，表示 n 个人。 

第 2 行包含 n 个用空格隔开的正整数T1,T2,…,Tn，其中第 i 个整数 Ti 表示编号为 i 的同学的信息传递对象是编号为 Ti 的同学，Ti ≤n 且 Ti ≠i。 

数据保证游戏一定会结束。

输出格式
输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。

数据范围
n≤200000
输入样例：
5
2 4 2 3 1
输出样例：
3

解法

每个人看做点 通讯的途径看做边的话 这里就是求最短的环。

应该可以使用搜索的方式获取最短的环

我们这里没使用这种方式 而是使用tarjan求环

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int maxn = 2e5 + 7;
 9 vector<int> E[maxn];
10 int vis[maxn];
11 int dfn[maxn], low[maxn], tot, n, ans = maxn;
12 stack<int> s;
13 
14 void tarjan(int x)
15 {
16     low[x] = dfn[x] = ++ tot;
17     s.push(x); vis[x] = 1;
18 
19     for (int i = 0; i < E[x].size(); i++) {
20         int v = E[x][i];
21         if (!dfn[v]) {
22             tarjan(v);
23             low[x] = min(low[x], low[v]);
24         }
25         else if (vis[v]) {
26             low[x] = min(low[x], dfn[v]);
27         }
28     }
29 
30     if (low[x] == dfn[x]) {
31         int cnt = 0;
32         while (1) {
33             int now = s.top();
34             s.pop();
35             vis[x] = 0;
36             cnt++;
37             if (now == x) break;
38         }
39         if (cnt > 1) ans = min(ans, cnt);
40     }
41 
42 }
43 
44 int main()
45 {
46     scanf("%d",&n );
47     for (int i = 1; i <= n; i++) {
48         int x;
49         scanf("%d", &x);
50         E[i].push_back(x);
51     }
52 
53     for (int i = 1; i <= n; i++) {
54         if (!dfn[i])
55             tarjan(i);
56     }
57 
58     cout << ans << endl;
59 
60     return 0;
61 }

还可以考虑使用并查集的办法 找到最小的并查集即可

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 
 6 const int N = 200000+1000;
 7 int fa[N],n,m,i,j,k,cnt,ans = 1e9;
 8 
 9 int find(int  x)
10 {
11     cnt++;
12     return fa[x]==x?x:find(fa[x]);
13 }
14 
15 
16 int main(){
17     cin >> n;
18     for(int i = 1;i <= n;i++)
19         fa[i] = i;
20     for(int i = 1;i <= n;i++){
21         int x;
22         cin >> x;
23         cnt = 0;
24         if(find(x) == i)
25             ans = min(ans,cnt);
26         else 
27             fa[i] = x;
28     }
29     
30     cout << ans;    
31     return 0;
32 }