前排Orz tarjan

tarjan算法在图的连通性方面有非常多的应用，dfn和low数组真是奥妙重重（并没有很搞懂反正背就完事了）

有向图强连通分量

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<stack>

 using namespace std;

 struct edge{

     int v,next;

 }a[];

 stack<int>s;

 int n,m,u,v,sum=,tt=-,ans=,h[],anss[],num[],nums[],tot=,tim=,dfn[],low[],head[];

 bool used[],isin[];

 void tarjan(int u){

     int v;

     used[u]=isin[u]=true;

     low[u]=dfn[u]=++tim;

     s.push(u);

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         v=a[tmp].v;

         if(!used[v]){

             tarjan(v);

             low[u]=min(low[u],low[v]);

         }else{

             if(isin[v])low[u]=min(low[u],dfn[v]);

         }

     }

     if(low[u]==dfn[u]){

         v=-;

         sum++;

         while(v!=u){

             v=s.top();

             s.pop();

             isin[v]=;

             num[v]=sum;

             nums[sum]++;

         }

     }

 }

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 int main(){

     memset(used,,sizeof(used));

     memset(head,-,sizeof(head));

     memset(h,-,sizeof(h));

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         add(u,v);

     }

     for(int i=;i<=n;i++){

         if(!used[i])tarjan(i);

     }

     tot=;

     for(int i=;i<=n;i++){

         for(int tmp=head[i];tmp!=-;tmp=a[tmp].next){

             if(num[i]!=num[a[tmp].v]){

                 h[num[i]]=++tot;

             }

         }

     }

     for(int i=;i<=sum;i++){

         if(nums[i]>)ans++;

     }

     printf("%d\n",ans);

     for(int i=;i<=sum;i++){

         if(h[i]==-){

              if(tt!=-||nums[i]==){

                 tt=-;

                 break;

              }else tt=i;

         }

     }

     if(tt==-)printf("-1");

     else for(int i=;i<=n;i++){

         if(num[i]==tt)printf("%d ",i);

     }

     return ;

 }

无向图割点

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 struct edge{

     int v,next;

 }a[];

 int t=,n,s,ss,u,v,tim=,sum=,tot=,head[],dfn[],low[];

 bool f=false,used[],ff[];

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void tarjan(int u,int fa){

     int v;

     dfn[u]=low[u]=++tim;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         v=a[tmp].v;

         if(!low[v]){

             tarjan(v,u);

             if(u==)sum++;

             low[u]=min(low[u],low[v]);

             if(u!=&&dfn[u]<=low[v]){

                 ff[u]=true;

             }

         }else if(v!=fa){

             low[u]=min(low[u],dfn[v]);

         }

     }

 }

 void dfs(int u){

     int v;

     used[u]=true;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         v=a[tmp].v;

         if(!used[v])dfs(v);

     }

 }

 int main(){

     while(scanf("%d",&s)&&s){

         printf("Network #%d\n",++t);

         memset(head,-,sizeof(head));

         memset(ff,,sizeof(ff));

         memset(dfn,,sizeof(dfn));

         memset(low,,sizeof(low));

         tot=n=sum=tim=;

         f=false;

         scanf("%d",&ss);

         add(s,ss);

         add(ss,s);

         n=max(n,max(s,ss));

         scanf("%d",&s);

         while(s){

             scanf("%d",&ss);

             add(s,ss);

             add(ss,s);

             n=max(n,max(s,ss));

             scanf("%d",&s);

         }

         tarjan(,-);

         if(sum>)ff[]=true;

         for(int i=;i<=n;i++){

             if(ff[i]){

                 memset(used,,sizeof(used));

                 f=used[i]=true;

                 sum=;

                 for(int j=;j<=n;j++){

                     if(!used[j]){

                         sum++;

                         dfs(j);

                     }

                 }

                 printf("  SPF node %d leaves %d subnets\n",i,sum);

             }

         }

         if(!f){

             printf("  No SPF nodes\n");

         }

         printf("\n");

     }

     return ;

 }

 /*

 1 2

 5 4

 3 1

 3 2

 3 4

 3 5

 0

 1 2

 2 3

 3 4

 4 5

 5 1

 0

 1 2

 2 3

 3 4

 4 6

 6 3

 2 5

 5 1

 0

 0

 --------

 Network #1

   SPF node 3 leaves 2 subnets

 Network #2

   No SPF nodes

 Network #3

   SPF node 2 leaves 2 subnets

   SPF node 3 leaves 2 subnets

 */

无向图点双连通分量

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<cmath>

 #include<stack>

 using namespace std;

 struct edge{

     int v,next;

 }a[];

 struct edge1{

     int u,v;

 };

 int n,m,u,v,tot=,tim=,bcctot=,bccnum[],head[],dfn[],low[],iscut[];

 vector<int>ans[];

 stack<edge1>s;

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void tarjan(int u,int fa){

     edge1 t;

     int v,son;

     dfn[u]=low[u]=++tim;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         v=a[tmp].v;

         if(v==fa)continue;

         t.u=u;

         t.v=v;

         if(!dfn[v]){

             s.push(t);

             son++;

             tarjan(v,u);

             low[u]=min(low[u],low[v]);

             if(low[v]>=dfn[u]){

                 iscut[u]=true;

                 ans[++bcctot].clear();

                 while(true){

                     edge1 tt=s.top();

                     s.pop();

                     if(bccnum[tt.u]!=bcctot){

                         ans[bcctot].push_back(tt.u);

                         bccnum[tt.u]=bcctot;

                     }

                     if(bccnum[tt.v]!=bcctot){

                         ans[bcctot].push_back(tt.v);

                         bccnum[tt.v]=bcctot;

                     }

                     if(tt.u==u&&tt.v==v)break;

                 }

             }

         }else if(dfn[v]<low[u]){

             s.push(t);

             low[u]=min(low[u],dfn[v]);

         }

     }

     if(fa<&&son==)iscut[u]=false;

 }

 int main(){

     memset(iscut,,sizeof(iscut));

     memset(head,-,sizeof(head));

     memset(low,,sizeof(low));

     memset(bccnum,,sizeof(bccnum));

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         add(u,v);

         add(v,u);

     }

     tarjan(,-);

     for(int i=;i<=bcctot;i++){

         printf("%d:",i);

         for(int j=;j<ans[i].size();j++){

             printf("%d ",ans[i][j]);

         }

         printf("\n");

     }

     return ;

 }

 /*

 6 7

 1 2

 2 3

 1 3

 3 4

 4 5

 3 5

 5 6

 --------

 1:5 6

 2:4 3 5

 3:2 1 3

 */

无向图求桥

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 struct edge{

     int u,v,next;

 }a[];

 int n,m,u,v,tot=,tim=,head[],dfn[],low[],ansu[],ansv[];

 void add(int u,int v){

     a[++tot].u=u;

     a[tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void tarjan(int u,int fa){

     int v;

     dfn[u]=low[u]=++tim;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         v=a[tmp].v;

         if(dfn[v]==){

             tarjan(v,u);

             low[u]=min(low[u],low[v]);

             if(low[v]>dfn[u]){

                 ansu[++ansu[]]=u;

                 ansv[++ansv[]]=v;

             }

         }else{

             if(dfn[v]<dfn[u]&&v!=fa){

                 low[u]=min(low[u],dfn[v]);

             }

         }

     }

 }

 int main(){

     memset(head,-,sizeof(head));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     ansu[]=;

     ansv[]=;

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         add(u,v);

         add(v,u);

     }

     tarjan(,-);

     printf("--------\n");

     for(int i=;i<=ansv[];i++){

         printf("%d %d\n",ansu[i],ansv[i]);

     }

     return ;

 }

 /*

 6 7

 1 2

 2 3

 1 3

 3 4

 4 5

 5 6

 6 4

 --------

 3 4

 */

无向图边双连通分量

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<cmath>

 using namespace std;

 struct edge{

     int v,next;

 }a[];

 int n,m,u,v,tot=,tim=,num=,head[],dfn[],low[],bl[];

 bool used[],bri[];

 vector<int>g[];

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void tarjan(int u,int fa){

     int v;

     dfn[u]=low[u]=++tim;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         v=a[tmp].v;

         if(dfn[v]==){

             tarjan(v,u);

             low[u]=min(low[u],low[v]);

             if(low[v]>dfn[u]){

                 bri[tmp]=true;

                 bri[tmp^]=true;

             }

         }else{

             if(dfn[v]<dfn[u]&&v!=fa){

                 low[u]=min(low[u],dfn[v]);

             }

         }

     }

 }

 void dfs(int u){

     used[u]=true;

     bl[u]=num;

     g[num].push_back(u);

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         int v=a[tmp].v;

         if(bri[tmp])continue;

         if(!used[v])dfs(v);

     }

 }

 int main(){

     memset(head,-,sizeof(head));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     memset(used,,sizeof(used));

     memset(bri,,sizeof(bri));

     memset(bl,,sizeof(bl));

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         add(u,v);

         add(v,u);

     }

     for(int i=;i<=n;i++){

         if(!dfn[i])tarjan(i,-);

     }

     for(int i=;i<=n;i++){

         if(!used[i]){

             num++;

             dfs(i);

         }

     }

     for(int i=;i<=num;i++){

         printf("%d: ",i);

         for(int j=;j<g[i].size();j++)printf("%d ",g[i][j]);

         printf("\n");

     }

     return ;

 }

最新文章

  1. click 事件 arguments.callee 每次点击自动* 2
  2. Prepared Java infrastructure for distributed scenarios
  3. Oracle表连接
  4. oracle数据库管理员简介、导入数据与导出数据
  5. JavaScript中的加号
  6. 自动化Cobbler安装
  7. Sans Serif 与 Serif 字体是什么意思？
  8. Nginx学习之二-配置项解析及编程实现
  9. Agile methodology
  10. （大数据工程师学习路径）第四步 SQL基础课程----SQL介绍及mysql的安装
  11. oracle导入dmp文件的2种方法
  12. Linux IPC实践(13) --System V IPC综合实践
  13. jloi2015
  14. 内建模块collections的使用
  15. php跨域发送请求原理以及同步异步问题
  16. TCP/IP协议详解内容总结（怒喷一口老血）
  17. 多网卡环境下Eureka服务注册IP选择问题
  18. mongodb--Profiling慢查询详解
  19. 关于MySQL中pymysql安装的问题。
  20. hibernate中.常见的hql查询语句

热门文章

  1. ZBrush破解版下载，ZBrush中文版下载
  2. MySQL的几个重要配置参数详解
  3. Java根据当前日期获得昨天的当前日期代码实现
  4. 【XSY2689】王子 - 网络流
  5. [置顶] 使用 maven 插件 maven-shade-plugin 对可执行 java 工程及其全部依赖 jar 进行打包
  6. BZOJ 3675 [Apio2014]序列分割 (斜率优化DP)
  7. BZOJ 4026 dC Loves Number Theory (主席树+数论+欧拉函数)
  8. java源码之LinkedHashMap
  9. UVALIVE 4256 Salesmen
  10. ZJOI—— 密码机（2003）