割点与桥的求解都有一个前提：所求的图是连通图，不连通的图没有割点
给每个顶点定义一个Low值, Low(u)表示从u出发, 经过一条其后代组成的路径和后向边, 所能到达的最小深度的顶点的编号(如果这个编号大于等于u的编号, 就说明它的后代无法到达比u深度更浅的顶点, 即无法到达u的祖先, 那么u就是个关节点, 具体做法是在DFS每次回溯后拿刚才扩展节点的Low与当前节点的DFN比较, 若low>=dfn则当前节点是割点).
Low(u)=min{DFN(u), min{Low(w)|w是u的儿子}, min{DFN(w)|(u,w) 是一条后向边}} DFN(u)是深搜过程中对顶点的编号值.
在求割点的同时就可以通过一个全局的栈求出点的双连通分量, 具体做法是在DFS每次由当前顶点u深入下一顶点v时, 就将边uv进栈, 若在函数返回后判断出v是割点, 则出栈, 直到uv出栈,刚才出栈的这些边就属于同一个点双连通分量.
在求割点的同时就可以通过一个全局的栈求出点的双连通分量, 具体做法是在DFS每次由当前顶点u深入下一顶点v时, 就将边uv进栈, 若在函数返回后判断出v是割点, 则出栈, 直到uv出栈,刚才出栈的这些边就属于同一个点双连通分量.
来看一下几个定义吧：
对dfs的搜索树的定义，这是必须首先明确的，搜索树是这样一棵树，他的顶点是图中的顶点，他的边（A，B）可以说是从图中的对应点A到对应点B的访问，也可以说，树的边(A,B)对应了图中的边（A，B），并且说明了B是从A经过这条边到达的
之后定义搜索顺序的方式：
像（A）这样，从U扩展W，W为一个未扩展到的顶点，那么边(U,V)叫树枝弧
像（B）这样从U扩展一条路，扩展到了V，后来返回到了U,结果有一条(U,V)，这时候V已经扩展，边(U,V)叫作前向弧
像 (C)这样，从U扩展到了V，然后再扩展V的，扩展V的时候发现有一条边（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 //题目中可能的最大点数
int DFN[M]; //深度优先搜索访问次序
int Low[M]; //能追溯到的最早的次序
vector <int> Edge[M]; //邻接表表示
int Belong[M];
int Index=0;
int CutVertexNum=0,CutVertexList[M]; //保存个点数目与割点 1-indexed
int BridgeNum=0,Bridgeu[M],Bridgev[M]; //保存割边数量与割边起始点 1-indexed
int BlockNum=0;vector <int> Block[M]; //保存块数目和块
int len,que[M];
int color=0; //color 用来记录连通分量个数
void DFS(int u,int parent)
{
int v,son=0, beVertexCut=0; //son记录的是点u的儿子数目
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]); //后向边
}
}
//非根节点且是割点 或者 根节点且儿子至少有两个
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为图中的点数
{
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.cppblog.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文章