poj 2186 强连通分支
scturtle
posted @ 2010年9月05日 01:34
in algorithm
, 2475 阅读
tarjan 485MS
原理: 在任何深度优先搜索中,同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说,强连通分量一定是有向图的某个深搜树子树。
定义dfn(u)为节点u的时间戳,low(u)为节点u或u的子树能追溯到的最小的栈中节点的dfn值。当dfs回溯时发现dfn(u)==low(u),则u是分量子树的根,从u到栈顶为一个连通分支里的。
#include<cstdio> #include<cstring> #include<vector> using namespace std; typedef vector<int>::iterator it; #define maxn 10001 int inline min(int a,int b){return a<b?a:b;} vector<int> g[maxn]; int dfn[maxn],low[maxn],stack[maxn]; int idx,top; bool instack[maxn]; int sc,f[maxn],cnt[maxn]; void tarjan(int u) { dfn[u]=low[u]=++idx; stack[top++]=u; instack[u]=1; for(it v=g[u].begin();v!=g[u].end();++v) if(!dfn[*v])//not visited tarjan(*v),low[u]=min(low[u],low[*v]); else if(instack[*v]) low[u]=min(low[u],dfn[*v]); if(dfn[u]==low[u])//find root { ++sc;cnt[sc]=0; do { f[stack[--top]]=sc; cnt[sc]++; instack[stack[top]]=0; } while(u!=stack[top]); } } int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int n,m,u,v; scanf("%d%d",&n,&m); while(m--) { scanf("%d%d",&u,&v); g[u].push_back(v); } idx=top=sc=0; memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); //for(int i=1;i<=n;i++) printf("%d ",f[i]); //缩点 int out[sc+1];memset(out,0,sizeof(out)); for(u=1;u<=n;u++) for(it v=g[u].begin();v!=g[u].end();++v) if(f[u]!=f[*v]) out[f[u]]++; int count=0,ans; for(int i=1;i<=sc && count<2;i++) if(out[i]==0) count++,ans=i; if(count==1) printf("%d\n",cnt[ans]); else puts("0"); }
kosaraju 360MS
步骤:
1. dfs原图得到拓扑序。
2. 按照拓扑序dfs反图,每个dfs树中的顶点都是一个连通分支里的。
#include<cstdio> #include<cstring> #include<vector> using namespace std; #define maxn 10001 typedef vector<int>::iterator it; vector<int> g[maxn],gr[maxn]; int t,gs[maxn];//toposort of g int fs,f[maxn];//result of SCC bool vit[maxn]; void dfs(int v) { vit[v]=true; for(it w=g[v].begin();w!=g[v].end();++w) if(!vit[*w]) dfs(*w); gs[t--]=v;//记录拓扑顺序(finish时间的反序) } void rdfs(int v) { vit[v]=true; f[v]=fs; for(it w=gr[v].begin();w!=gr[v].end();++w) if(!vit[*w]) rdfs(*w); } int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int n,m,v,w; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) g[i].clear(), gr[i].clear(); while(m--) { scanf("%d%d",&v,&w); g[v].push_back(w); gr[w].push_back(v); } //正向 memset(vit,false,sizeof(vit)); t=n; for(int i=1;i<=n;i++) if(!vit[i]) dfs(i); //拓扑序 //for(int i=1;i<=n;i++) //printf("%d ",gs[i]); //puts(""); //逆向 memset(vit,false,sizeof(vit)); fs=0; for(int i=1;i<=n;i++)//拓扑序遍历反图 if(!vit[gs[i]]) ++fs, rdfs(gs[i]); //输出每个点所属的强联通号 1~fs //for(int i=1;i<=n;i++) //printf("%d ",f[i]); //for poj 2186 缩点 int out[fs+1],num[fs+1]; memset(out,0,sizeof(out)); memset(num,0,sizeof(num)); for(int v=1;v<=n;v++) { num[f[v]]++; for(it w=g[v].begin();w!=g[v].end();++w) if(f[v]!=f[*w]) out[f[v]]++; } int cnt=0,ans; for(int i=1;i<=fs && cnt<2;i++) if(out[i]==0) cnt++,ans=i; if(cnt==1) printf("%d\n",num[ans]); else puts("0"); }
gabow 532MS
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <cstdlib> #define maxn 10001 using namespace std; int n,m; vector<int> g[maxn]; int pre[maxn],path[maxn],sc[maxn],s[maxn],ct[maxn]; int cnt0,cnt1,p,top; bool outis0[maxn]; void scDfs(int w) { int v,i; pre[w]=cnt0++; s[top++]=w;path[p++]=w; for(i=0;i<g[w].size();i++) { v=g[w][i]; if(pre[v]==-1) scDfs(v); else if(sc[v]==-1) while(pre[path[p-1]]>pre[v]) p--; } if(path[p-1]!=w) return; else p--; do sc[s[--top]]=cnt1; while(s[top]!=w); cnt1++; } int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int v,w,i,j; scanf("%d%d",&n,&m); for(i=0;i<n;i++) g[i].clear(); for(i=0;i<m;i++) { scanf("%d%d",&v,&w); g[v-1].push_back(w-1); } p=cnt0=cnt1=top=0; for(int i=0;i<n;i++) sc[i]=pre[i]=-1; for(int i=0;i<n;i++) if(sc[i]==-1) scDfs(i); //缩点 for(i=0;i<cnt1;i++) {outis0[i]=1;ct[i]=0;} for(i=0;i<n;i++) { ct[sc[i]]++; for(j=0;j<g[i].size();j++) if(sc[i]!=sc[g[i][j]]) outis0[sc[i]]=0; } int index,count=0; for(i=0;i<cnt1;i++) if(outis0[i]) {index=i;count++;} if(count==1) printf("%d\n",ct[index]); else printf("0\n"); return 0; }