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

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. }
  29. //注意，图可能并不连通
  30. inline void Tarjan_SCC(){
  31.     for(int i=1;i<=n;++i){
  32.         if(!dfn[i]) Tarjan_SCC(i);
  33.     }
  34. }

练习

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

双联通分量

定义与性质

割桥和边双

算法原理

代码

  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. }
  32. inline void Tarjan_EBC(){
  33.     for(int i=1;i<=n;++i){
  34.         if(!dfn[i]) Tarjan_EBC(i,0);
  35.     }
  36. }

练习

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

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

割点和点双

算法原理

代码

  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. }
  41. inline void Tarjan_PBC(){
  42.     for(int i=1;i<=n;++i){
  43.         if(!dfn[i]) Tarjan_PBC(i,0);
  44.     }
  45. }

练习

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

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

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