由于图论的算法不太熟悉，今天早上考了一道NOIP原题打爆了。。所以我要好好学下最小环。。
最小环的算法有并查集、trajan、反图。这里从简单的开始写
反图：设G为原图,F图为反图。
step1：对G遍历记录每个点的退出顺序dfn[]
对于下面这个图遍历序列为1 2 3 5 （5 3 2 ）1 3（4 1）
括号括起来的是返回值
dfn=5 3 2 4 1
G图
step2:对反图F 按照dfn的反序对反图进行dfs遍历
访问过程：1 4 （return）2 5 3 （return）
F图如下：
得出两个强联通分量就是14 ； 2 5 3；
在最小环处理的问题上要注意两个问题
1.图的强联通问题：必须保证图的联通性如果不行，那么反复dfs知道找到所有点为止
2.单个的点不是环及dfs2中得出cnt=1的情况要舍去
程序：
# include <cstdio> # include <cstring> # include <iostream> using namespace std; struct rec{ int pre,to; }; const int MAXN=1000005; int n,m,tot1=0,tot2=0; int dfn[MAXN],head1[MAXN],head2[MAXN]; bool vis[MAXN]; rec a[MAXN],b[MAXN]; int adde1(int u,int v) //正图前向星 { tot1++; a[tot1].pre=head1[u]; a[tot1].to=v; head1[u]=tot1; } int adde2(int u,int v)//反图前向星 { tot2++; b[tot2].pre=head2[u]; b[tot2].to=v; head2[u]=tot2; } int dfs1(int u) //求dfn序 { vis[u]=true; for (int i=head1[u];i!=0;i=a[i].pre) { int v=a[i].to; if (vis[v]==true) continue; dfs1(v); } dfn[++dfn[0]]=u; } int dfs2(int u) //求环 { vis[u]=true; for (int i=head2[u];i!=0;i=b[i].pre) { int v=b[i].to; if (vis[v]==true) continue; dfs2(v); } printf("%d ",u); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); adde1(u,v); adde2(v,u);//正图A，反图B； } memset(dfn,0,sizeof(dfn)); memset(vis,false,sizeof(vis)); for (int i=1;i<=n;i++) if (vis[i]==false) dfs1(i); //得出dfn /* printf("***************************************************** "); printf("调试输出dfn[]: "); for (int i=1;i<=dfn[0];i++) printf("%d ",dfn[i]); for (int i=1;i<=first[0];i++) printf("%d ",first[i]); printf(" "); printf("***************************************************** "); */ memset(vis,false,sizeof(vis)); int cnt=0; for (int i=dfn[0];i>0;i--) //反序搞一搞求强联通块 { if (vis[dfn[i]]==true) continue; cnt++; printf("强联通块# %d :",cnt); dfs2(dfn[i]); printf(" "); } return 0; }
上述代码就可以求一个图中最小环的个数复杂度是O（2*n）应该来说比较快，这里放道模板题目：