$Description$
给定一个有向图,每个点只有一条出边.求图里的最小环.
$Sol$
使得这个题不难的地方就在于每个点只有一条出边叭.
一边连边一边更新答案.首先当然是初始$f[i]=i$,然后连$(u,v)$边的时候如果$find(u)==find(v)$,说明$v$已经有一条路径到$u$了,现在这条边又是从$u$到$v$,这不就构成一个环了嘛.于是只要算出环的大小更新答案.$d[i]$表示从$i$结点开始走,一直走到无路可走(再走就会走到走过的点)经过的点.每次连边如果不构成环就$d[u]=d[v]+1$.如果构成环那环的大小一定是$d[v]+1$.而且此时不要更新$d[u]$,因为它已经不可能在别的环里了.
$over.$
$Code$
#include<iostream> #include<cstdio> using namespace std; int read() { int x=0,y=1;char c; c=getchar(); while(c<‘0‘||c>‘9‘) {if(c==‘-‘) y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } int n,ans=210000000; int f[200010],d[200010]; int find(int x) { if(f[x]==x) return x; int tmp=f[x]; f[x]=find(f[x]); d[x]+=d[tmp]; return f[x]; } void solve(int u,int v) { int fu=find(u),fv=find(v); if(fu!=fv) {f[fu]=fv;d[u]=d[v]+1;} else {ans=min(ans,d[v]+1);} } int main() { //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read(); for(register int i=1;i<=n;i++) f[i]=i; for(register int i=1;i<=n;i++) { int x=read(); solve(i,x); } printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/forward777/p/11406279.html
