在一個無向連通圖中，如果任意去掉一個定點i及依附于i的所有邊后得到的圖仍然連通，
則稱該圖為“2-連通圖”。否則，若得到多個連通分量，則該圖不是雙連通的，頂點i被稱為
“割點 ”。
簡單的說，在雙連通圖中，任何一對頂點都至少存在兩條路徑可以互相到達。圖的連通
性不會任何一個頂點的影響。這個性質(zhì)具有許多重要的應(yīng)用價值，例如現(xiàn)實中的通訊網(wǎng)絡(luò)部署，
出于可靠性和容錯性的考慮，在結(jié)構(gòu)上應(yīng)考慮多連通性，盡量避免割點的存在。這樣就算一個
通信節(jié)點損毀，也不會對其他節(jié)點的通信造成影響。
無向圖的極大雙連通子圖被稱為2-連通分量。一個無向圖都具有一個或多個2-連通分量。
如果圖本身是一個雙連通圖，那么它本身是自己唯一的2-連通分量。一個無向圖具有2個或以
上2分量時，不難看出它的任意兩個2分量最多只可能有一個公共頂點。因為如果有多于一個公
共頂點，就可以證明這兩個2分量實際上可以組成一個更大的2分量，從而引起矛盾。進一步還
可以得出同一條邊不可能處于多個二分量之中，因為一條邊有兩個頂點，如果一條邊屬于多個
二分量，則相當(dāng)于兩個頂點可以同時處于多個二分量之中，這與前述矛盾。
綜上，所有二分量實際上把圖劃分為了不相交的子集，連接不同二分量的邊成為割邊。
可以利用深度優(yōu)先搜索求2-連通分量。如果生成樹的root是割點，當(dāng)且僅當(dāng)它有多于一個
子女。如果生成樹的非根節(jié)點是割點，當(dāng)且僅當(dāng)它沒有一個后代可以通過后向邊回到它的祖先。
根據(jù)這些條件，我們定義一個點的時間戳為深度優(yōu)先數(shù)，代表著頂點在深度優(yōu)先搜索時被訪問
的先后次序，記為D。如果D(i)<D(j)，表明i點在serch過程中先于j點被訪問。為了比較方便的
知道一個頂點是不是割點，對頂點定義參數(shù)low，low[i]為從i或其后代出發(fā)，通過后向邊所能達
到的最小深度優(yōu)先數(shù)。
low[i]=min{ D(i) , min{low[j]|j為i的子女} , min{D(k)|(i,k)為后向邊} }
//edge為無向圖邊表，n為頂點數(shù), e總邊數(shù)
void TwoCC(int n,int e)
{
//D,low
//S 棧保存二分量邊
int *D=(int *)malloc(sizeof(int)*(n+1));
int *low=(int *)malloc(sizeof(int)*(n+1));
int *S=(int *)malloc(sizeof(int)*(2*e));
memset(D,0,sizeof(D));
memset(low,0,sizeof(low));
for(int i=0; i<n; i++){
// 若未訪問則以此為起點尋找二分量
if(D[i]==0)
DFS(i,-1,1,D,low,S,0);
}
}
// 從u做DFS，v是u之父,num為目前深度優(yōu)先數(shù)
// top --> S
void DFS(int u,int v,int num,int D[],int low[],int S[],int top){
D[u]=low[u]=num++;
Edge* l = edge[u];
// 搜索所有與i鄰接之頂點
while(l){
if( v!= l->dest && D[l->dest] < D[u] ){
// 連通分量邊壓棧
S[top++]=u;
S[top++] = l->dest;
}
if( D[l->dest] == 0 ){
DFS(l->dest,u,num,D,low,S,top);
low[u]=( low[u] < low[l->dest] )? low[u] : low[l->dest];
// 無后向邊，分量結(jié)束
if( low[l->dest] == 0 ){
cout<<"A 2-CC found:"<<endl;
do{
int x = S[--top];
int y = S[--top];
cout<<x<<" "<<y<<endl;
if( x== u && y == l->dest ) break;
}while(1)
}
}
else
if( l->dest != v ){
// 如果l-dest已經(jīng)被訪問過，并且不等于父頂點v，證明有后向邊更新low
low[u] = ( low[u] < D[l->dest] ) ? low[u] : D[l->dest];
}
l=l->next;
}
}