割點與橋的求解都有一個前提：所求的圖是連通圖，不連通的圖沒有割點
給每個頂點定義一個Low值, Low(u)表示從u出發(fā), 經(jīng)過一條其后代組成的路徑和后向邊, 所能到達的最小深度的頂點的編號(如果這個編號大于等于u的編號, 就說明它的后代無法到達比u深度更淺的頂點, 即無法到達u的祖先, 那么u就是個關節(jié)點, 具體做法是在DFS每次回溯后拿剛才擴展節(jié)點的Low與當前節(jié)點的DFN比較, 若low>=dfn則當前節(jié)點是割點).
Low(u)=min{DFN(u), min{Low(w)|w是u的兒子}, min{DFN(w)|(u,w) 是一條后向邊}} DFN(u)是深搜過程中對頂點的編號值.
在求割點的同時就可以通過一個全局的棧求出點的雙連通分量, 具體做法是在DFS每次由當前頂點u深入下一頂點v時, 就將邊uv進棧, 若在函數(shù)返回后判斷出v是割點, 則出棧, 直到uv出棧,剛才出棧的這些邊就屬于同一個點雙連通分量.
在求割點的同時就可以通過一個全局的棧求出點的雙連通分量, 具體做法是在DFS每次由當前頂點u深入下一頂點v時, 就將邊uv進棧, 若在函數(shù)返回后判斷出v是割點, 則出棧, 直到uv出棧,剛才出棧的這些邊就屬于同一個點雙連通分量.
來看一下幾個定義吧：
對dfs的搜索樹的定義，這是必須首先明確的，搜索樹是這樣一棵樹，他的頂點是圖中的頂點，他的邊（A，B）可以說是從圖中的對應點A到對應點B的訪問，也可以說，樹的邊(A,B)對應了圖中的邊（A，B），并且說明了B是從A經(jīng)過這條邊到達的
之后定義搜索順序的方式：
像（A）這樣，從U擴展W，W為一個未擴展到的頂點，那么邊(U,V)叫樹枝弧
像（B）這樣從U擴展一條路，擴展到了V，后來返回到了U,結果有一條(U,V)，這時候V已經(jīng)擴展，邊(U,V)叫作前向弧
像 (C)這樣，從U擴展到了V，然后再擴展V的，擴展V的時候發(fā)現(xiàn)有一條邊（V，U）,那么邊(V,U），也就是說有一條指向祖先的邊，叫作反向弧
(D)指向非祖先的訪問過的點，叫作橫向弧
在無向圖中，沒有可能dfs出前向弧或者橫向弧，只有a、c
樹T的根是圖G的割點，當且僅當其在T中至少有兩個兒子(程序中，我們使用的是son來記錄)
代碼：（Sosi coded）這個代碼求出了圖的割點 橋與二連通分量圖
#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;
/*
此問題是獲得圖的割，橋，與點連通分量圖
*/
#define M 5000 //題目中可能的最大點數(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)€點數(shù)目與割點 1-indexed
int BridgeNum=0,Bridgeu[M],Bridgev[M]; //保存割邊數(shù)量與割邊起始點 1-indexed
int BlockNum=0;vector <int> Block[M]; //保存塊數(shù)目和塊
int len,que[M];
int color=0; //color 用來記錄連通分量個數(shù)
void DFS(int u,int parent)
{
int v,son=0, beVertexCut=0; //son記錄的是點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; //求割點
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é)點且是割點 或者 根節(jié)點且兒子至少有兩個
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)); //所有的塊號都大于等于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) //縮點形成新圖,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;
}
/*
此算法正常工作的基礎是圖是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;
}
[圖的雙連通性問題例題]
備用交換機
求圖的割點，直接輸出。
pku 3177(3352) Redundant Paths
求橋，收縮邊雙連通子圖，構造邊雙連通圖。
POI 1999 倉庫管理員 Store-keeper
求點雙連通子圖。
一些題目：
http://www.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文章