一.基本概念
1.桥：是存在于无向图中的这样的一条边，如果去掉这一条边，那么整张无向图会分为两部分，这样的一条边称为桥无向连通图中，如果删除某边后，图变成不连通，则称该边为桥。
2.割点：无向连通图中，如果删除某点后，图变成不连通，则称该点为割点。
二：tarjan算法在求桥和割点中的应用
1.割点：1）当前节点为树根的时候，条件是“要有多余一棵子树”（如果只有一颗子树，去掉这个点也没有影响，如果有两颗子树，去掉这点，两颗子树就不连通了。）
2）当前节点U不是树根的时候，条件是“low[v]>=dfn[u]”，也就是在u之后遍历的点，能够向上翻，最多到u，如果能翻到u的上方，那就有环了，去掉u之后，图仍然连通。
保证v向上最多翻到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<iostream> 2 using namespace std; 3 #include<cstdio> 4 #include<cstring> 5 #include<vector> 6 #define N 201 7 vector<int>G[N]; 8 int n,m,low[N],dfn[N]; 9 bool is_cut[N]; 10 int father[N]; 11 int tim=0; 12 void input() 13 { 14 scanf("%d%d",&n,&m); 15 int a,b; 16 for(int i=1;i<=m;++i) 17 { 18 scanf("%d%d",&a,&b); 19 G[a].push_back(b);/*邻接表储存无向边*/ 20 G[b].push_back(a); 21 } 22 } 23 void Tarjan(int i,int Father) 24 { 25 father[i]=Father;/*记录每一个点的父亲*/ 26 dfn[i]=low[i]=tim++; 27 for(int j=0;j<G[i].size();++j) 28 { 29 int k=G[i][j]; 30 if(dfn[k]==-1) 31 { 32 Tarjan(k,i); 33 low[i]=min(low[i],low[k]); 34 } 35 else if(Father!=k)/*假如k是i的父亲的话，那么这就是无向边中的重边，有重边那么一定不是桥*/ 36 low[i]=min(low[i],dfn[k]);//dfn[k]可能！=low[k]，所以不能用low[k]代替dfn[k],否则会上翻过头了。 37 } 38 } 39 void count() 40 { 41 int rootson=0; 42 Tarjan(1,0); 43 for(int i=2;i<=n;++i) 44 { 45 int v=father[i]; 46 if(v==1) 47 rootson++;/*统计根节点子树的个数，根节点的子树个数>=2,就是割点*/ 48 else{ 49 if(low[i]>=dfn[v])/*割点的条件*/ 50 is_cut[v]=true; 51 } 52 } 53 if(rootson>1) 54 is_cut[1]=true; 55 for(int i=1;i<=n;++i) 56 if(is_cut[i]) 57 printf("%d\n",i); 58 for(int i=1;i<=n;++i) 59 { 60 int v=father[i]; 61 if(v>0&&low[i]>dfn[v])/*桥的条件*/ 62 printf("%d,%d\n",v,i); 63 } 64 65 } 66 int main() 67 { 68 input(); 69 memset(dfn,-1,sizeof(dfn)); 70 memset(father,0,sizeof(father)); 71 memset(low,-1,sizeof(low)); 72 memset(is_cut,false,sizeof(is_cut)); 73 count(); 74 return 0; 75 }
原文：http://www.cnblogs.com/suishiguang/p/6390559.html