题目描述：
n个点，n条边，求最小环
首先，我们知道，这至少一个环，m个点m条边（一个大的n个点的图形，按照连通性分成几份）
然后在环上变形，大概就是这样
所以，我们可以任意选择一个点，都能进入环，并且两次到达一个一个环的其中一个端点，
环的长度就是nw - (dfn[st] -1 )
注意，因为环可能被两个方向进入，所以直接减肯定不行，（长度会包含链上的点）
然后就可以愉快的写出代码了
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,ans,cnt; const int N=2e5+3; int nx[N],stp[N]; void bfs(int st) { int mn=cnt; while(!stp[st] ) stp[st]=++cnt,st=nx[st]; if(stp[st]>mn) ans=min(ans,cnt-stp[st]+1); } int main() { scanf("%d",&n); ans=n; for(int i=1;i<=n;i++) scanf("%d",&nx[i]); for(int i=1;i<=n;i++) if(!stp[i] ) bfs(i); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/xwww666666/p/11821582.html