首页 > 代码库 > 强连通分量的模版 Kosaraju+Tarjan+Garbow
强连通分量的模版 Kosaraju+Tarjan+Garbow
PS：在贴出代码之前，我得说明内容来源——哈尔滨工业大学出版的《图论及应用》。虽然有一些错误的地方，但是不得不说是初学者该用的书。
从效率的角度来说，Kosaraju <Tarjan<Garbow。一般网上有前两种的代码和分析。Garbow算法是Tarjan的另一种实现，但是Garbow效率更高。
不过从复杂度来说，三种算法的时间（空间）复杂度都是O(m +n)。
模版的调用方式很简单，初始化，建图，调用Tarjan(n)或者Kosaraju(n)或者 Garbow(n)， scc就是强连通分量的个数。
（1）Kosaraju
//Kosarajuconst int N =10010, M=50010;struct node{ int to, next;}edge[M],edge2[M]; //edge是逆图,edge2是原图int dfn[N], head[N], head2[N], belg[N], num[N];//dfn时间戳//belg记录每个点属于哪个连通分量,num记录强连通分量点的个数bool vis[N];int cnt,cnt1,scc,tot,tot1;void dfs1(int u){ vis[u]=1; for(int k=head2[u];k!=-1;k=edge2[k].next) if(!vis[edge2[k].to]) dfs1(edge2[k].to); dfn[++cnt1]=u;}void dfs2(int u){ vis[u]=1; cnt++; belg[u]=scc; for(int k=head[u];k!=-1;k=edge[k].next) if(!vis[edge[k].to]) dfs2(edge[k].to);}void Kosaraju(int n){ memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis)); cnt1=scc=0; for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i); memset(vis,0,sizeof(vis)); for(int i=cnt1;i>0;i--) if(!vis[dfn[i]]) { cnt=0; ++scc; dfs2(dfn[i]); num[scc] = cnt; }}void init(){ tot=tot1=0; memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); memset(num,0,sizeof(num));}void addedge(int i,int j){ edge2[tot1].to=j; edge2[tot1].next=head2[i];head2[i]=tot1++; edge[tot].to=i; edge[tot].next=head[j];head[j]=tot++;}
(2)Tarjan
//Tarjanconst int N =1010, M=100010;struct node{ int to, next;}edge[M];int head[N], low[N], dfn[N], sta[N], belg[N], num[N];bool vis[N];int scc,index,top, tot;void tarbfs(int u){ int i,j,k,v; low[u]=dfn[u]=++index; sta[top++]=u; vis[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(!dfn[v]) { tarbfs(v); if(low[u]>low[v]) low[u]=low[v]; } else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v]; } if(dfn[u]==low[u]) { scc++; do { v=sta[--top]; vis[v]=0; belg[v]=scc; num[scc]++; } while(v!=u) ; }}void Tarjan(int n){ memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); index=scc=top=0; for(int i=1;i<=n;i++) if(!dfn[i]) tarbfs(i);}void init(){ tot=0; memset(head,-1,sizeof(head));}void addedge(int i,int j){ edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;}
(3)Garbow//Garbowconst int N =110, M=100010;struct node{ int to, next;;}edge[M];int stk[N],stk2[N],head[N],low[N],belg[N];int cn,cm,tot,scc,lay;int Garbowbfs(int cur,int lay){ stk[++cn]=cur; stk2[++cm]=cur; low[cur]=++lay; for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!low[v]) Garbowbfs(v,lay); else if(!belg[v]) while(low[stk2[cm]]>low[v]) cm--; } if(stk2[cm]==cur) { cm--; scc++; do belg[stk[cn]]=scc; while(stk[cn--]!=cur) ; } return 0;}void Garbow(int n){ scc=lay=0; memset(belg,0,sizeof(belg)); memset(low,0,sizeof(low)); for(int i=0;i<n;i++) if(!low[i]) Garbowbfs(i,lay);}void init(){ memset(head,-1,sizeof(-1));}void addedge(int i,int j){ edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;}
强连通分量的模版 Kosaraju+Tarjan+Garbow
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。