【NOIP2015提高组】信息传递

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

因为本题涉及到连通成环的问题，因此可以考虑用并查集来做

注意：此题不能用扁平化，因为我们要统计用了多少次才能到达其祖先，相当于要记录树中的dep值，但由于会构成环，所以用普通的并查集来做方便一些

code:

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 const int N=2e5+100; 
 4 using namespace std;
 5 int n,ans=2147483647,l,sum;
 6 int a[N];
 7 int f[N],cnt;
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
11     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x*f;
13 }
14 inline void write(int x)
15 {
16     if(x<0)x=-x,putchar('-');
17     if(x>9)write(x/10);
18     putchar(x%10+'0');
19 }
20 int find(int fa){
21     cnt++;//统计次数 
22     if(f[fa]==fa)return fa;
23     return find(f[fa]);//普通的并查集 
24 }
25 int main()        
26 {
27     n=read();
28     for(int i=1;i<=n;i++)f[i]=i;//一定要初始，因为最开始本身的祖先为自己 
29     for(int i=1;i<=n;i++){
30         cnt=0;//每做一次要不断的清 0 因为我们是求某一个点经过几轮构成环 
31         a[i]=read();
32         if(find(a[i])==i){//如果构成环 
33             ans=min(ans,cnt);//求构成环的最少轮数 
34         }
35         else{//若没有构成环 
36             f[i]=a[i];//否则令 i的父亲为 a[i] 
37         }
38     }
39     printf("%d
",ans);
40     return 0;
41 }
42 /*
43 5
44 2 4 2 3 1
45 */

【NOIP2015提高组】 信息传递

【NOIP2015提高组】信息传递