[关闭]
@KirinBill 2017-12-03T14:28:46.000000Z 字数 12849 阅读 2067

Tarjan的三个算法

学习笔记 图论

目录


强连通分量

定义与性质

算法原理

代码

  1. void Tarjan_SCC(int u){
  2. static int idx=0;
  3. static int low[MAXN];
  4. static bool inS[MAXN];
  5. static stack<int> stk;
  6. dfn[u]=low[u]=++idx;
  7. stk.push(u);
  8. inS[u]=true;
  9. for(int i=he[u],v;i;i=ed[i].nex){
  10. v=ed[i].to;
  11. if(!dfn[v]){
  12. Tarjan_SCC(v);
  13. low[u]=min(low[u],low[v]);
  14. }
  15. else if(inS[v]) low[u]=min(low[u],dfn[v]);
  16. }
  17. if(dfn[u]==low[u]){
  18. ++tot;
  19. int now;
  20. do{
  21. now=stk.top();
  22. stk.pop();
  23. inS[now]=false;
  24. scc[now]=tot;
  25. }while(now!=u);
  26. }
  27. }
  28. //注意,图可能并不连通
  29. inline void Tarjan_SCC(){
  30. for(int i=1;i<=n;++i){
  31. if(!dfn[i]) Tarjan_SCC(i);
  32. }
  33. }

练习

  1. #include <cstdio>
  2. #include <stack>
  3. #include <queue>
  4. #include <algorithm>
  5. using std::stack;
  6. using std::min;
  7. using std::max;
  8. using std::queue;
  9. const int MAXN=1e4+5,MAXM=1e5+5;
  10. int n,m,tot;
  11. int he[MAXN],w[MAXN],scc[MAXN];
  12. struct line{int to,nex;}ed[MAXM];
  13. namespace preG{
  14. int he[MAXN],dfn[MAXN],w[MAXN];
  15. struct line{int to,nex;}ed[MAXM];
  16. inline void addE(int u,int v){
  17. static int cnt=0;
  18. ed[++cnt]=(line){v,he[u]};
  19. he[u]=cnt;
  20. }
  21. void Tarjan_SCC(int u){
  22. static int idx=0;
  23. static int low[MAXN];
  24. static bool inS[MAXN];
  25. static stack<int> stk;
  26. dfn[u]=low[u]=++idx;
  27. stk.push(u);
  28. inS[u]=true;
  29. for(int i=he[u],v;i;i=ed[i].nex){
  30. v=ed[i].to;
  31. if(!dfn[v]){
  32. Tarjan_SCC(v);
  33. low[u]=min(low[u],low[v]);
  34. }
  35. else if(inS[v]) low[u]=min(low[u],dfn[v]);
  36. }
  37. if(dfn[u]==low[u]){
  38. ++tot;
  39. int now;
  40. do{
  41. now=stk.top();
  42. stk.pop();
  43. inS[now]=false;
  44. scc[now]=tot;
  45. ::w[tot]+=w[now];
  46. }while(now!=u);
  47. }
  48. }
  49. inline void Tarjan_SCC(){
  50. for(int i=1;i<=n;++i){
  51. if(!dfn[i]) Tarjan_SCC(i);
  52. }
  53. }
  54. }
  55. inline void addE(int u,int v){
  56. static int cnt=0;
  57. ed[++cnt]=(line){v,he[u]};
  58. he[u]=cnt;
  59. }
  60. int inD[MAXN];
  61. inline void rebuild(){
  62. using preG::he;
  63. using preG::ed;
  64. preG::Tarjan_SCC();
  65. for(int u=1;u<=n;++u){
  66. for(int i=he[u],v;i;i=ed[i].nex){
  67. v=ed[i].to;
  68. if(scc[u]!=scc[v]){
  69. addE(scc[u],scc[v]);
  70. ++inD[scc[v]];
  71. }
  72. }
  73. }
  74. }
  75. inline int DAG_DP(){
  76. static int dp[MAXN];
  77. static queue<int> que;
  78. for(int i=1;i<=tot;++i){
  79. dp[i]=w[i];
  80. if(!inD[i]) que.push(i);
  81. }
  82. int u;
  83. while(que.size()){
  84. u=que.front();
  85. que.pop();
  86. for(int i=he[u],v;i;i=ed[i].nex){
  87. v=ed[i].to;
  88. dp[v]=max(dp[v],dp[u]+w[v]);
  89. if(--inD[v]==0) que.push(v);
  90. }
  91. }
  92. int ret=0;
  93. for(int i=1;i<=tot;++i)
  94. ret=max(ret,dp[i]);
  95. return ret;
  96. }
  97. int main(){
  98. using preG::addE;
  99. using preG::w;
  100. scanf("%d%d",&n,&m);
  101. for(int i=1;i<=n;++i)
  102. scanf("%d",&w[i]);
  103. for(int i=1,u,v;i<=m;++i){
  104. scanf("%d%d",&u,&v);
  105. addE(u,v);
  106. }
  107. rebuild();
  108. printf("%d",DAG_DP());
  109. return 0;
  110. }
  1. #include <cstdio>
  2. #include <stack>
  3. #include <algorithm>
  4. using std::stack;
  5. using std::min;
  6. using std::max;
  7. const int MAXN=105;
  8. int n,tot,ans1,ans2;
  9. int he[MAXN],scc[MAXN],dfn[MAXN],inD[MAXN],outD[MAXN];
  10. struct line{int to,nex;}ed[MAXN*MAXN];
  11. inline void addE(int u,int v){
  12. static int cnt=0;
  13. ed[++cnt]=(line){v,he[u]};
  14. he[u]=cnt;
  15. }
  16. void Tarjan_SCC(int u){
  17. static int idx;
  18. static int low[MAXN];
  19. static bool inS[MAXN];
  20. static stack<int> stk;
  21. dfn[u]=low[u]=++idx;
  22. stk.push(u);
  23. inS[u]=true;
  24. for(int i=he[u],v;i;i=ed[i].nex){
  25. v=ed[i].to;
  26. if(!dfn[v]){
  27. Tarjan_SCC(v);
  28. low[u]=min(low[u],low[v]);
  29. }
  30. else if(inS[v]) low[u]=min(low[u],dfn[v]);
  31. }
  32. if(dfn[u]==low[u]){
  33. ++tot;
  34. int now;
  35. do{
  36. now=stk.top();
  37. stk.pop();
  38. inS[now]=false;
  39. scc[now]=tot;
  40. }while(now!=u);
  41. }
  42. }
  43. inline void Tarjan_SCC(){
  44. for(int i=1;i<=n;++i){
  45. if(!dfn[i]) Tarjan_SCC(i);
  46. }
  47. }
  48. inline void solve(){
  49. Tarjan_SCC();
  50. for(int u=1;u<=n;++u){
  51. for(int i=he[u],v;i;i=ed[i].nex){
  52. v=ed[i].to;
  53. if(scc[u]!=scc[v]) ++outD[scc[u]],++inD[scc[v]];
  54. }
  55. }
  56. int in=0,out=0;
  57. for(int i=1;i<=tot;++i){
  58. if(!inD[i]) ++in;
  59. if(!outD[i]) ++out;
  60. }
  61. ans1=in;
  62. ans2=max(in,out);
  63. }
  64. int main(){
  65. scanf("%d",&n);
  66. for(int i=1,v;i<=n;++i){
  67. while(scanf("%d",&v),v)
  68. addE(i,v);
  69. }
  70. solve();
  71. if(tot==1) printf("1\n0");
  72. else printf("%d\n%d",ans1,ans2);
  73. return 0;
  74. }
  1. #include <cstdio>
  2. #include <stack>
  3. #include <algorithm>
  4. using std::stack;
  5. using std::min;
  6. const int MAXN=10005,MAXM=50005;
  7. int n,m,tot;
  8. int he[MAXN],scc[MAXN],dfn[MAXN],sz[MAXN],outD[MAXN];
  9. struct line{int to,nex;}ed[MAXM];
  10. inline void addE(int u,int v){
  11. static int cnt=0;
  12. ed[++cnt]=(line){v,he[u]};
  13. he[u]=cnt;
  14. }
  15. void Tarjan_SCC(int u){
  16. static int idx;
  17. static int low[MAXN];
  18. static bool inS[MAXN];
  19. static stack<int> stk;
  20. dfn[u]=low[u]=++idx;
  21. stk.push(u);
  22. inS[u]=true;
  23. for(int i=he[u],v;i;i=ed[i].nex){
  24. v=ed[i].to;
  25. if(!dfn[v]){
  26. Tarjan_SCC(v);
  27. low[u]=min(low[u],low[v]);
  28. }
  29. else if(inS[v]) low[u]=min(low[u],dfn[v]);
  30. }
  31. if(dfn[u]==low[u]){
  32. ++tot;
  33. int now;
  34. do{
  35. now=stk.top();
  36. stk.pop();
  37. inS[now]=false;
  38. scc[now]=tot;
  39. ++sz[tot];
  40. }while(now!=u);
  41. }
  42. }
  43. inline void Tarjan_SCC(){
  44. for(int i=1;i<=n;++i){
  45. if(!dfn[i]) Tarjan_SCC(i);
  46. }
  47. }
  48. inline int solve(){
  49. Tarjan_SCC();
  50. for(int u=1;u<=n;++u){
  51. for(int i=he[u],v;i;i=ed[i].nex){
  52. v=ed[i].to;
  53. if(scc[u]!=scc[v]) ++outD[scc[u]];
  54. }
  55. }
  56. bool flag=false;
  57. int ret;
  58. for(int i=1;i<=tot;++i){
  59. if(!outD[i]){
  60. if(flag) return 0;
  61. else{
  62. ret=sz[i];
  63. flag=true;
  64. }
  65. }
  66. }
  67. return ret;
  68. }
  69. int main(){
  70. scanf("%d%d",&n,&m);
  71. for(int i=1,u,v;i<=m;++i){
  72. scanf("%d%d",&u,&v);
  73. addE(u,v);
  74. }
  75. printf("%d",solve());
  76. return 0;
  77. }

双联通分量

定义与性质

割桥和边双

算法原理

代码

  1. void Tarjan_EBC(int u,int fa){
  2. static int idx;
  3. static int low[MAXN];
  4. static bool inS[MAXN];
  5. static stack<int> stk;
  6. dfn[u]=low[u]=++idx;
  7. stk.push(u);
  8. inS[u]=true;
  9. for(int i=he[u],v;i;i=ed[i].nex){
  10. v=ed[i].to;
  11. if(!dfn[v]){
  12. Tarjan_EBC(v,u);
  13. //边(u,v)是割桥
  14. if(low[v]>dfn[u]) cut[i]=true;
  15. else low[u]=min(low[u],low[v]);
  16. }
  17. else if(v!=fa && inS[v])
  18. low[u]=min(low[u],dfn[v]);
  19. }
  20. if(dfn[u]==low[u]){
  21. ++tot;
  22. int now;
  23. do{
  24. now=stk.top();
  25. stk.pop();
  26. inS[now]=false;
  27. ebc[now]=tot;
  28. }while(now!=u);
  29. }
  30. }
  31. inline void Tarjan_EBC(){
  32. for(int i=1;i<=n;++i){
  33. if(!dfn[i]) Tarjan_EBC(i,0);
  34. }
  35. }

练习

这方面的练习题似乎不多。。。

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::min;
  4. const int MAXN=5005,MAXM=10005;
  5. int n,m;
  6. int he[MAXN],dfn[MAXN],low[MAXN],deg[MAXN];
  7. bool G[MAXN][MAXN];
  8. struct line{int to,nex;}ed[MAXM<<1];
  9. inline void addE(int u,int v){
  10. static int cnt=0;
  11. ed[++cnt]=(line){v,he[u]};
  12. he[u]=cnt;
  13. }
  14. void Tarjan_EBC(int u,int fa){
  15. static int idx;
  16. dfn[u]=low[u]=++idx;
  17. for(int i=he[u],v;i;i=ed[i].nex){
  18. v=ed[i].to;
  19. if(!dfn[v]){
  20. Tarjan_EBC(v,u);
  21. low[u]=min(low[u],low[v]);
  22. }
  23. else if(v!=fa && dfn[v]<dfn[u])
  24. low[u]=min(low[u],dfn[v]);
  25. }
  26. }
  27. inline void Tarjan_EBC(){
  28. for(int i=1;i<=n;++i){
  29. if(!dfn[i]) Tarjan_EBC(i,0);
  30. }
  31. }
  32. inline int cal(){
  33. Tarjan_EBC();
  34. for(int u=1;u<=n;++u){
  35. for(int i=he[u],v;i;i=ed[i].nex){
  36. v=ed[i].to;
  37. if(low[u]!=low[v]) ++deg[low[u]];
  38. }
  39. }
  40. int ret=0;
  41. for(int i=1;i<=n;++i){
  42. if(deg[i]==1) ++ret;
  43. }
  44. return ret+1>>1;
  45. }
  46. int main(){
  47. scanf("%d%d",&n,&m);
  48. for(int i=1,u,v;i<=m;++i){
  49. scanf("%d%d",&u,&v);
  50. G[u][v]=G[v][u]=true;
  51. }
  52. for(int i=1;i<n;++i){
  53. for(int j=i+1;j<=n;++j){
  54. if(G[i][j]) addE(i,j),addE(j,i);
  55. }
  56. }
  57. printf("%d",cal());
  58. return 0;
  59. }

割点和点双

算法原理

代码

  1. void Tarjan_PBC(int u,int fa){
  2. static int idx;
  3. static int low[MAXN];
  4. static stack<int> stk;
  5. dfn[u]=low[u]=++idx;
  6. int son=0;
  7. for(int i=he[u],v;i;i=ed[i].nex){
  8. v=ed[i].to;
  9. if(!dfn[v]){
  10. ++son;
  11. stk.push(i);
  12. Tarjan_PBC(v,u);
  13. low[u]=min(low[u],low[v]);
  14. if(low[v]>=dfn[u]){
  15. cut[u]=true;
  16. ++tot;
  17. line *e;
  18. do{
  19. e=&ed[stk.top()];
  20. stk.pop();
  21. if(blg[e->frm]!=tot){
  22. pbc[tot].push_back(e->frm);
  23. blg[e->frm]=tot;
  24. }
  25. if(blg[e->to]!=tot){
  26. pbc[tot].push_back(e->to);
  27. blg[e->to]=tot;
  28. }
  29. }while(e->frm!=u || e->to!=v);
  30. }
  31. else low[u]=min(low[u],low[v]);
  32. }
  33. else if(v!=fa && dfn[v]<dfn[u]){
  34. stk.push(i);
  35. low[u]=min(low[u],dfn[v]);
  36. }
  37. }
  38. if(!fa && son<2) cut[u]=false;
  39. }
  40. inline void Tarjan_PBC(){
  41. for(int i=1;i<=n;++i){
  42. if(!dfn[i]) Tarjan_PBC(i,0);
  43. }
  44. }

练习

  1. #include <cstdio>
  2. #include <stack>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. using std::stack;
  7. using std::min;
  8. using std::vector;
  9. const int MAXN=1005,MAXM=1e6+5;
  10. int n,m,tot,idx,cnt;
  11. int he[MAXN],blg[MAXN],dfn[MAXN],col[MAXN];
  12. bool cannt[MAXN][MAXN],oddCir[MAXN];
  13. vector<int> pbc[MAXN];
  14. struct line{int frm,to,nex;}ed[MAXN*MAXN];
  15. inline void addE(int u,int v){
  16. ed[++cnt]=(line){u,v,he[u]};
  17. he[u]=cnt;
  18. }
  19. void Tarjan_PBC(int u,int fa){
  20. static int low[MAXN];
  21. static stack<int> stk;
  22. dfn[u]=low[u]=++idx;
  23. for(int i=he[u],v;i;i=ed[i].nex){
  24. v=ed[i].to;
  25. if(!dfn[v]){
  26. stk.push(i);
  27. Tarjan_PBC(v,u);
  28. if(low[v]>=dfn[u]){
  29. pbc[++tot].clear();
  30. line *e;
  31. do{
  32. e=&ed[stk.top()];
  33. stk.pop();
  34. if(blg[e->frm]!=tot){
  35. pbc[tot].push_back(e->frm);
  36. blg[e->frm]=tot;
  37. }
  38. if(blg[e->to]!=tot){
  39. pbc[tot].push_back(e->to);
  40. blg[e->to]=tot;
  41. }
  42. }while(e->frm!=u || e->to!=v);
  43. }
  44. else low[u]=min(low[u],low[v]);
  45. }
  46. else if(v!=fa && dfn[v]<dfn[u]){
  47. stk.push(i);
  48. low[u]=min(low[u],dfn[v]);
  49. }
  50. }
  51. }
  52. inline void Tarjan_PBC(){
  53. for(int i=1;i<=n;++i){
  54. if(!dfn[i]) Tarjan_PBC(i,0);
  55. }
  56. }
  57. bool dye(int u){
  58. for(int i=he[u],v;i;i=ed[i].nex){
  59. v=ed[i].to;
  60. if(blg[v]!=blg[u]) continue;
  61. if(col[v]==col[u]) return false;
  62. if(col[v]==-1){
  63. col[v]=col[u]^1;
  64. if(!dye(v)) return false;
  65. }
  66. }
  67. return true;
  68. }
  69. inline void cal_oddCir(){
  70. for(int i=1;i<=tot;++i){
  71. memset(col,-1,sizeof(col));
  72. for(int j=0;j<pbc[i].size();++j)
  73. blg[pbc[i][j]]=i;
  74. col[pbc[i][0]]=0;
  75. if(!dye(pbc[i][0])){
  76. for(int j=0;j<pbc[i].size();++j)
  77. oddCir[pbc[i][j]]=true;
  78. }
  79. }
  80. }
  81. inline void clear(){
  82. cnt=tot=idx=0;
  83. memset(dfn,0,sizeof(dfn));
  84. memset(cannt,false,sizeof(cannt));
  85. memset(he,0,sizeof(he));
  86. memset(oddCir,false,sizeof(oddCir));
  87. memset(blg,0,sizeof(blg));
  88. }
  89. int main(){
  90. while(scanf("%d%d",&n,&m),n && m){
  91. clear();
  92. for(int i=1,u,v;i<=m;++i){
  93. scanf("%d%d",&u,&v);
  94. cannt[u][v]=cannt[v][u]=true;
  95. }
  96. for(int i=1;i<n;++i){
  97. for(int j=i+1;j<=n;++j){
  98. if(!cannt[i][j])
  99. addE(i,j),addE(j,i);
  100. }
  101. }
  102. Tarjan_PBC();
  103. cal_oddCir();
  104. int ans=0;
  105. for(int i=1;i<=n;++i){
  106. if(!oddCir[i]) ++ans;
  107. }
  108. printf("%d\n",ans);
  109. }
  110. return 0;
  111. }
  1. #include <cstdio>
  2. #include <stack>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. using std::stack;
  7. using std::min;
  8. using std::vector;
  9. const int MAXN=5e4+5;
  10. int n,idx,tot,cnt,ans1;
  11. int he[MAXN],dfn[MAXN],blg[MAXN];
  12. long long ans2;
  13. bool cut[MAXN];
  14. vector<int> pbc[MAXN];
  15. struct line{int frm,to,nex;}ed[MAXN<<1];
  16. inline void addE(int u,int v){
  17. ed[++cnt]=(line){u,v,he[u]};
  18. he[u]=cnt;
  19. }
  20. void Tarjan_PBC(int u,int fa){
  21. static int low[MAXN];
  22. static stack<int> stk;
  23. dfn[u]=low[u]=++idx;
  24. int son=0;
  25. for(int i=he[u],v;i;i=ed[i].nex){
  26. v=ed[i].to;
  27. if(!dfn[v]){
  28. ++son;
  29. stk.push(i);
  30. Tarjan_PBC(v,u);
  31. if(low[v]>=dfn[u]){
  32. cut[u]=true;
  33. pbc[++tot].clear();
  34. line *e;
  35. do{
  36. e=&ed[stk.top()];
  37. stk.pop();
  38. if(blg[e->frm]!=tot){
  39. pbc[tot].push_back(e->frm);
  40. blg[e->frm]=tot;
  41. }
  42. if(blg[e->to]!=tot){
  43. pbc[tot].push_back(e->to);
  44. blg[e->to]=tot;
  45. }
  46. }while(e->frm!=u || e->to!=v);
  47. }
  48. else low[u]=min(low[u],low[v]);
  49. }
  50. else if(dfn[v]<dfn[u]){
  51. stk.push(i);
  52. low[u]=min(low[u],dfn[v]);
  53. }
  54. }
  55. if(!fa && son<2) cut[u]=false;
  56. }
  57. inline void solve(){
  58. Tarjan_PBC(1,0);
  59. if(tot==1){
  60. ans1=2;
  61. ans2=(long long)pbc[1].size()*(pbc[1].size()-1)>>1;
  62. return;
  63. }
  64. ans1=0,ans2=1;
  65. for(int i=1,cnt,lim;i<=tot;++i){
  66. cnt=0,lim=pbc[i].size();
  67. for(int j=0;j<lim;++j){
  68. if(cut[pbc[i][j]]) ++cnt;
  69. }
  70. if(cnt==1) ++ans1,ans2*=lim-cnt;
  71. }
  72. }
  73. inline void clear(){
  74. idx=cnt=tot=0;
  75. memset(dfn,0,sizeof(dfn));
  76. memset(he,0,sizeof(he));
  77. memset(blg,0,sizeof(blg));
  78. memset(cut,false,sizeof(cut));
  79. }
  80. int main(){
  81. int T=0;
  82. while(scanf("%d",&n),n){
  83. ++T;
  84. clear();
  85. for(int i=1,u,v;i<=n;++i){
  86. scanf("%d%d",&u,&v);
  87. addE(u,v),addE(v,u);
  88. }
  89. solve();
  90. printf("Case %d: %d %lld\n",T,ans1,ans2);
  91. }
  92. return 0;
  93. }

[7]: "国家队清华集训2012 解题报告"

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注