割點(diǎn)與橋的求解都有一個(gè)前提：所求的圖是連通圖，不連通的圖沒有割點(diǎn)
給每個(gè)頂點(diǎn)定義一個(gè)Low值, Low(u)表示從u出發(fā), 經(jīng)過一條其后代組成的路徑和后向邊, 所能到達(dá)的最小深度的頂點(diǎn)的編號(hào)(如果這個(gè)編號(hào)大于等于u的編號(hào), 就說明它的后代無法到達(dá)比u深度更淺的頂點(diǎn), 即無法到達(dá)u的祖先, 那么u就是個(gè)關(guān)節(jié)點(diǎn), 具體做法是在DFS每次回溯后拿剛才擴(kuò)展節(jié)點(diǎn)的Low與當(dāng)前節(jié)點(diǎn)的DFN比較, 若low>=dfn則當(dāng)前節(jié)點(diǎn)是割點(diǎn)).
Low(u)=min{DFN(u), min{Low(w)|w是u的兒子}, min{DFN(w)|(u,w) 是一條后向邊}} DFN(u)是深搜過程中對(duì)頂點(diǎn)的編號(hào)值.
在求割點(diǎn)的同時(shí)就可以通過一個(gè)全局的棧求出點(diǎn)的雙連通分量, 具體做法是在DFS每次由當(dāng)前頂點(diǎn)u深入下一頂點(diǎn)v時(shí), 就將邊uv進(jìn)棧, 若在函數(shù)返回后判斷出v是割點(diǎn), 則出棧, 直到uv出棧,剛才出棧的這些邊就屬于同一個(gè)點(diǎn)雙連通分量.
在求割點(diǎn)的同時(shí)就可以通過一個(gè)全局的棧求出點(diǎn)的雙連通分量, 具體做法是在DFS每次由當(dāng)前頂點(diǎn)u深入下一頂點(diǎn)v時(shí), 就將邊uv進(jìn)棧, 若在函數(shù)返回后判斷出v是割點(diǎn), 則出棧, 直到uv出棧,剛才出棧的這些邊就屬于同一個(gè)點(diǎn)雙連通分量.
來看一下幾個(gè)定義吧：
對(duì)dfs的搜索樹的定義，這是必須首先明確的，搜索樹是這樣一棵樹，他的頂點(diǎn)是圖中的頂點(diǎn)，他的邊（A，B）可以說是從圖中的對(duì)應(yīng)點(diǎn)A到對(duì)應(yīng)點(diǎn)B的訪問，也可以說，樹的邊(A,B)對(duì)應(yīng)了圖中的邊（A，B），并且說明了B是從A經(jīng)過這條邊到達(dá)的
之后定義搜索順序的方式：
像（A）這樣，從U擴(kuò)展W，W為一個(gè)未擴(kuò)展到的頂點(diǎn)，那么邊(U,V)叫樹枝弧
像（B）這樣從U擴(kuò)展一條路，擴(kuò)展到了V，后來返回到了U,結(jié)果有一條(U,V)，這時(shí)候V已經(jīng)擴(kuò)展，邊(U,V)叫作前向弧
像 (C)這樣，從U擴(kuò)展到了V，然后再擴(kuò)展V的，擴(kuò)展V的時(shí)候發(fā)現(xiàn)有一條邊（V，U）,那么邊(V,U），也就是說有一條指向祖先的邊，叫作反向弧
(D)指向非祖先的訪問過的點(diǎn)，叫作橫向弧
在無向圖中，沒有可能dfs出前向弧或者橫向弧，只有a、c
樹T的根是圖G的割點(diǎn)，當(dāng)且僅當(dāng)其在T中至少有兩個(gè)兒子(程序中，我們使用的是son來記錄)
代碼：（Sosi coded）這個(gè)代碼求出了圖的割點(diǎn) 橋與二連通分量圖
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;
/*
此問題是獲得圖的割，橋，與點(diǎn)連通分量圖
*/
#define M 5000 //題目中可能的最大點(diǎn)數(shù)
int DFN[M]; //深度優(yōu)先搜索訪問次序
int Low[M]; //能追溯到的最早的次序
vector <int> Edge[M]; //鄰接表表示
int Belong[M];
int Index=0;
int CutVertexNum=0,CutVertexList[M]; //保存?zhèn)€點(diǎn)數(shù)目與割點(diǎn) 1-indexed
int BridgeNum=0,Bridgeu[M],Bridgev[M]; //保存割邊數(shù)量與割邊起始點(diǎn) 1-indexed
int BlockNum=0;vector <int> Block[M]; //保存塊數(shù)目和塊
int len,que[M];
int color=0; //color 用來記錄連通分量個(gè)數(shù)
void DFS(int u,int parent)
{
int v,son=0, beVertexCut=0; //son記錄的是點(diǎn)u的兒子數(shù)目
Belong[u]=-color; que[++len]=u;
DFN[u]=Low[u]=Index++;
for (int e=0;e<Edge[u].size();e++)
{
v=Edge[u][e];
if(v!=parent)
{
if(Belong[v]==0) //樹枝邊
{
DFS(v,u);son++;
Low[u]=min(Low[v],Low[u]);
if(Low[v]>=DFN[u])
{
beVertexCut=1; //求割點(diǎn)
BlockNum++;
while(que[len]!=v){ Block[BlockNum].push_back(que[len]);cout<<que[len--]<<" ";}
Block[BlockNum].push_back(que[len]);Block[BlockNum].push_back(u);
cout<<que[len--]<<" "<<u<<endl;
}
if(Low[v]==DFN[v]) Bridgeu[++BridgeNum]=u,Bridgev[BridgeNum]=v; //求割邊
}
else Low[u]=min(Low[u],DFN[v]); //后向邊
}
}
//非根節(jié)點(diǎn)且是割點(diǎn) 或者 根節(jié)點(diǎn)且兒子至少有兩個(gè)
if((parent&& beVertexCut)||(!parent&&son>1)) CutVertexList[++CutVertexNum]=u;
Belong[u]=color;
}
void dfs(int N)
{
memset(DFN,-1,sizeof(DFN));
memset(Low,-1,sizeof(Low));
memset(CutVertexList,-1,sizeof(CutVertexList));
memset(Bridgeu,-1,sizeof(Bridgeu));
memset(Bridgev,-1,sizeof(Bridgev));
memset(Belong,0,sizeof(Belong)); //所有的塊號(hào)都大于等于1
for(int i=0;i<N;i++)
{
if(!Belong[i])
{
++color,len=0,DFSCUT(i,0);
if(len>1||DFN[i]==Index)
{
BlockNum++;
while(len>1){ Block[BlockNum].push_back(que[len]);cout<<que[len--]<<" ";}
Block[BlockNum].push_back(i);
cout<<i<<endl;
}
}
}
}
void reshape(int N) //縮點(diǎn)形成新圖,N為圖中的點(diǎn)數(shù)
{
if(color==1)
{
cout<<"CutVertexNum "<<CutVertexNum<<endl;
for(int i=1;i<=CutVertexNum;i++)
{
cout<<CutVertexList[i]<<" ";
}
cout<<endl;
cout<<"BridgeNum "<<BridgeNum<<endl;
for(int i=1;i<=BridgeNum;i++)
{
cout<<Bridgeu[i]<<" to "<<Bridgev[i]<<endl;
}
cout<<endl;
cout<<"Color"<<color<<endl;
for(int i=0;i<N;i++)
cout<<Belong[i]<<" ";
cout<<endl;
cout<<"Block"<<BlockNum<<endl;
for(int i=1;i<=BlockNum;i++)
{
for(int j=0;j<Block[i].size();j++)
{
cout<<Block[i][j]<<" ";
}
cout<<endl;
}
}
else
cout<<"It`s not a connected graph"<<endl;
}
/*
此算法正常工作的基礎(chǔ)是圖是0-indexed的。
*/
int main()
{
Edge[0].push_back(1),Edge[0].push_back(2);
Edge[1].push_back(0),Edge[1].push_back(2);
Edge[2].push_back(0),Edge[2].push_back(1),Edge[2].push_back(3);
Edge[3].push_back(2),Edge[3].push_back(4);
Edge[4].push_back(5);
Edge[5].push_back(4);
int N=6;
dfs(N);
reshape(N);
return 0;
}
[圖的雙連通性問題例題]
備用交換機(jī)
求圖的割點(diǎn)，直接輸出。
pku 3177(3352) Redundant Paths
求橋，收縮邊雙連通子圖，構(gòu)造邊雙連通圖。
POI 1999 倉庫管理員 Store-keeper
求點(diǎn)雙連通子圖。
一些題目：
http://m.shnenglu.com/Uriel/articles/121169.html
http://www.chenyajun.com/tag/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F
http://www.cnblogs.com/zhjjla/archive/2010/05/21/1741180.html
http://www.robin47.com/archives/423
Reference：
http://www.byvoid.com/blog/biconnect/ byvoid的NX文章