目标是查找一个图中的最小环
主要用了并查集,看了一下算法标签才写出来的
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n;
int a[N],fa[N];
int res=0x3f3f3f3f;
int getfather(int x)
{
if(fa[x]==x) return x;
else
return getfather(fa[x]);//和模板的区别是没有路径压缩,等到最后发现有环的时候才能全部遍历一遍得出环的边数
}
int gf(int last,int x,int step)//特殊的Getfather,返回边数而不是父节点
//这里的last不是上一个点,而是是否走到发现有环的地方
{
if(fa[x]==last) return step+1;
return gf(last,fa[x],step+1);
}
void join(int x,int y)//x->y
{
int a=getfather(x);
int b=getfather(y);
if(a!=b)
fa[x]=y;
else
{
int tmp=gf(a,y,0);
res=min(tmp+1,res);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
join(i,a[i]);
}
cout<<res;
}