洛谷P2611信息传递（思维环形题，并查集）

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <vector>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <cstring>
 9 using namespace std;
10 int a[1000005];
11 int n;
12 int ans=1e9;
13 
14 void so(int last,int t,int y)
15 {
16     if(t>ans) return;//剪枝优化退出
17     if(t>n) return;//死循环退出
18     if(a[last]==y)//找到一个解比较后退出
19     {
20         ans=min(ans,t);
21         return;
22     }
23 
24     so(a[last],t+1,y);
25 }
26 
27 
28 int main()
29 {
30     ios::sync_with_stdio(false); cin.tie(0);
31 
32     cin>>n;
33     for(int i=1;i<=n;i++) cin>>a[i];
34 
35     for(int i=1;i<=n;i++)
36     {
37         so(i,1,i);
38     }
39 
40     cout<<ans<<endl;
41 
42     return 0;
43 }

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <vector>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <cstring>
 9 using namespace std;
10 int a[1000005];
11 int fa[1000005];//父节点
12 int ra[1000005];//深度
13 int n;
14 int ans=1e9;
15 
16 void so(int last,int t,int y)
17 {
18     if(fa[last])//fa[last]有了这次函数给的y值了,说明碰头成环了,求深度需要巧妙考虑=这一步走的步数-第一次那个值的步数即可!
19     {
20         if(fa[last]==y) ans=min(ans,t-ra[last]);
21         return;
22     }
23 
24     fa[last]=y;
25     ra[last]=t;
26     so(a[last],t+1,y);
27 }
28 
29 
30 int main()
31 {
32     ios::sync_with_stdio(false); cin.tie(0);
33 
34     cin>>n;
35     for(int i=1;i<=n;i++) cin>>a[i];
36 
37     for(int i=1;i<=n;i++)//成一个环遍历一次会标记掉多点(这一圈)到时候直接返回节省很多时间,多个环仅仅多标记几次而已(几次内肯定能把所有环圈标记完一一直接返回)
38     {
39         so(i,0,i);
40     }
41 
42     cout<<ans<<endl;
43 
44     return 0;
45 }