UVA 796 Critical Links（模板题）(无向图求桥)

<题目链接>

题目大意：

无向连通图求桥，并将桥按顺序输出。

解题分析；

无向图求桥的模板题，下面用了kuangbin的模板。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <map>

 #include <vector>

 using namespace std;

 const int N = 1e4+;

 const int M = 1e5+;

 struct Edge{

     int to,next;

     bool cut;//是否为桥的标记

 }edge[M];

 int head[N],tot,n;

 int low[N],dfn[N],Stack[N];

 int Index,top;

 bool Instack[N],cut[N];

 int add_block[N];//删除一个点后增加的连通块

 int bridge;

 void init(){

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

     memset(dfn,,sizeof(dfn));

     memset(Instack,false,sizeof(Instack));

     memset(add_block,,sizeof(add_block));

     memset(cut,false,sizeof(cut));

     Index=top=bridge=tot = ;

 }

 void addedge(int u,int v){

     edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;

     head[u] = tot++;

 }

 void Tarjan(int u,int pre){

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

     Stack[top++] = u;

     Instack[u] = true;

     int son = ;

     for(int i = head[u];i != -;i = edge[i].next){

         int v = edge[i].to;

         if(v == pre)continue;

         if( !dfn[v] ){

             son++;

             Tarjan(v,u);

             if(low[u] > low[v])low[u] = low[v];

             if(low[v] > dfn[u]){    //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<low(v)

                 bridge++;

                 edge[i].cut = true;     //正反两边都标记为桥

                 edge[i^].cut = true;

             }

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

                 cut[u] = true;   //该点为割点

                 add_block[u]++;

             }

         }

         else if( low[u] > dfn[v])low[u] = dfn[v];

     }

     if(u == pre && son > )cut[u] = true;  //若u为根，且分支数>1，则u割点

     if(u == pre)add_block[u] = son - ;

     Instack[u] = false;

     top--;

 }

 void solve(){

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

         if( !dfn[i] )

             Tarjan(i,i);

     printf("%d critical links\n",bridge);

     vector<pair<int,int> >ans;          /*--   将桥按顺序输出  --*/

     for(int u = ;u <= n;u++)

         for(int i = head[u];i != -;i = edge[i].next)

             if(edge[i].cut && edge[i].to > u){

                 ans.push_back(make_pair(u,edge[i].to));

             }

     sort(ans.begin(),ans.end());

     for(int i = ;i < ans.size();i++)

         printf("%d - %d\n",ans[i].first-,ans[i].second-);

     printf("\n");

 }

 //处理重边

 /*map<int,int>mapit;

 inline bool isHash(int u,int v)

 {

     if(mapit[u*N+v])return true;

     if(mapit[v*N+u])return true;

     mapit[u*N+v] = mapit[v*N+u] = 1;

     return false;

 }*/

 int main(){

     while(scanf("%d",&n) == ){

         init();

         int u,k,v;

         //mapit.clear();

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

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

             u++;

             //这样加边，要保证正边和反边是相邻的，建无向图

             while(k--){

                 scanf("%d",&v);

                 v++;

                 if(v <= u)continue;

                 //if(isHash(u,v))continue;

                 addedge(u,v);

                 addedge(v,u);

             }

         }

         solve();

     }

     return ;

 }

2018-10-18