一.基本概念

    1.桥：若无向连通图的边割集中只有一条边，则称这条边为割边或者桥 (离散书上给出的定义。。

    通俗的来说就是无向连通图中的某条边，删除后得到的新图联通分支至少为2(即不连通；

    2.割点：若无向连通图的点割集中只有一个点，则称这个点为割点或者关节点 ；

    通俗的来说就是无向连通图中的某条边，删除后得到的新图连通分支至少为2；

 

二：tarjan算法求割点和桥

    1.割点：1）当前节点为树根的时候，条件是“要有多余一棵子树”；

　　　　     如果这有一颗子树，去掉这个点也没有影响，如果有两颗子树，去掉这点，两颗子树就不连通了；

                  2）当前节点u不是树根的时候，条件是“low[v]>=dfn[u]”，也就是在u之后遍历的点，能够向上翻，

　　　　　　最多到u，如果能翻到u的上方，那就有环了，去掉u之后，图仍然连通。

    2.桥：若一条无向边（u，v）是桥，

                  1）当且仅当无向边（u，v）是树枝边，需要满足dfn(u)<low(v)，即v向上翻不到u及其以上的点，

　　　　　　那么u--v之间一定能够有1条或者多条边不能删去， 因为他们之间有部分无环，是桥，

　　　　　　如果v能上翻到u那么u--v就是一个环，删除其中一条路径后，仍然是连通的。

    3.注意点：1）求桥的时候：因为边是无方向的，所以父亲孩子节点的关系需要自己规定一下，

                     在tarjan的过程中if（v不是u的父节点） low[u]=min(low[u],dfn[v]);

                     因为如果v是u的父亲，那么这条无向边就被误认为是环了。

                     2）找桥的时候：注意看看有没有重边，有重边的边一定不是桥，也要避免误判。

      4.也可以先进行tarjan()，求出每一个点的dfn和low，并记录dfs过程中的每个点的父节点，

　　  遍历所有点的low，dfn来寻找桥和割点

 

代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const int MAXN=1e5+10; 8 vector
          
            mp[MAXN]; 9 bool is_cut[MAXN];10 int n, m, count=0;11 int low[MAXN], dfn[MAXN], pre[MAXN];//pre[u]记录u的父亲节点编号12 //dfn[u]记录节点u在DFS过程中被遍历到的次序号，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小13 14 void tarjan(int u, int fu){15     pre[u]=fu;//记录当前u的父亲节点16     dfn[u]=low[u]=count++;17     for(int i=0; i
           
            =dfn[v]){36 is_cut[v]=true;37 }38 }39 if(rootson>1) is_cut[1]=true;40 puts("割点为：");41 for(int i=1; i<=n; i++){ //输出割点42 if(is_cut[i]){43 printf("%d ", i);44 }45 }46 puts("\n桥为：");47 for(int i=1; i<=n; i++){48 int v=pre[i];49 if(v>0&&low[i]>dfn[v]){50 printf("%d %d\n", v, i);51 }52 }53 puts("");54 }55 56 int main(void){57 scanf("%d%d", &n, &m);58 for(int i=0; i
           
          
         
        
       
      

 

求桥的另一种写法(更快一点):

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5  6 const int MAXN = 1e5 + 10; 7  8 struct node{ 9     int v, next, use;10 }edge[MAXN << 2];11 12 bool bridge[MAXN];13 int low[MAXN], dfn[MAXN], vis[MAXN];14 int head[MAXN], pre[MAXN], ip, sol, count;15 16 void init(void){17     memset(head, -1, sizeof(head));18     memset(vis, false, sizeof(vis));19     memset(bridge, false, sizeof(bridge));20     count = sol = ip = 0;21 }22 23 void addedge(int u, int v){24     edge[ip].v = v;25     edge[ip].use = 0;26     edge[ip].next = head[u];27     head[u] = ip++;28 }29 30 void tarjan(int u){31     vis[u] = 1;32     dfn[u] = low[u] = count++;33     for(int i = head[u]; i != -1; i = edge[i].next){34         if(!edge[i].use){35             edge[i].use = edge[i ^ 1].use = 1;36             int v = edge[i].v;37             if(!vis[v]){38                 pre[v] = u;39                 tarjan(v);40                 low[u] = min(low[u], low[v]);41                 if(dfn[u] < low[v]){42                     sol++;43                     bridge[v] = true;44                 }45             }else if(vis[v] == 1){46                 low[u] = min(low[u], dfn[v]);47             }48         }49     }50     vis[u] = 2;51 }52 53 int main(void){54     int n, m, q, x, y, cas = 1;55     while(~scanf("%d%d", &n, &m)){56         if(!n && !m) break;57         init();58         for(int i = 0; i < m; i++){59             scanf("%d%d", &x, &y);60             addedge(x, y);61             addedge(y, x);62         }63         pre[1] = 1;64         tarjan(1);65         for(int i = 1; i <= n; i++){66             if(bridge[i]) cout << i << " " << pre[i] << endl;67         }68     }69     return 0;70 }
        
       
      

 

以上参考博客：