本人水平有限,题解不到为处,请多多谅解
本蒟蒻谢谢大家观
题目:传送门
因为本题涉及到连通成环的问题,因此可以考虑用并查集来做
注意:此题不能用扁平化,因为我们要统计用了多少次才能到达其祖先,相当于要记录树中的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\n",ans); 40 return 0; 41 } 42 /* 43 5 44 2 4 2 3 1 45 */