图上求最小环

最近做了道水题题，信息传递，题目要求就是求出有向图的最小环。

做完乍一看题解有好多好多种办法，在此整理一下。

我对于这道题的做法是：

由于每个点最多连出一条边，所以可能存在两个环相连的情况，所以对于入度为0的点删掉就好，然后不断删不断删，

直到删到图上仅有环，就一个一个求一求环的大小，取最小的那一个。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 200005
 6 
 7 using namespace std;
 8 
 9 int nxt[maxn],ans=2147483647,ind[maxn],n;
10 bool vis[maxn];
11 
12 inline void cancel(int k)
13 {
14     int e=nxt[k];
15     ind[k]=0; ind[nxt[k]]--; nxt[k]=-1;
16     if(ind[e]==0) cancel(e);
17 }
18 
19 inline void dfs(int x_now,int st,int len)
20 {
21     if(x_now==st&&len!=0)
22     {
23         vis[x_now]=true;
24         ans=min(ans,len);
25         return;
26     }
27     else
28     {
29         vis[nxt[x_now]]=true;
30         dfs(nxt[x_now],st,len+1);
31     }
32     return;
33 }
34 
35 int main()
36 {
37     scanf("%d",&n);
38     for(int i=1;i<=n;i++)
39     {
40         scanf("%d",&nxt[i]);
41         ind[nxt[i]]++;
42     }
43     for(int i=1;i<=n;i++)
44         if(ind[i]==0&&nxt[i]!=-1) cancel(i);
45     for(int i=1;i<=n;i++)
46         if(nxt[i]!=-1&&!vis[i]) dfs(i,i,0);
47     printf("%d
",ans);
48     return 0;
49 }

一开始我还想用缩点求每个强连通分量的大小，后来一想，强联通分量是极大的子图，所以对于大环中有小环的情况，它只能求出

大环而求不出小环。

例如：

所以这种愚蠢的想法就被pass了。

还有一种做法就是用带权并查集做，权维护的是该点到自己父节点的距离。

如果某一条边连接了两个父节点相同的点，说明它们构成环，环的大小是...，