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