在一個無向連通圖中,如果任意去掉一個定點i及依附于i的所有邊后得到的圖仍然連通,
則稱該圖為“2-連通圖”。否則,若得到多個連通分量,則該圖不是雙連通的,頂點i被稱為
“割點 ”。
    簡單的說,在雙連通圖中,任何一對頂點都至少存在兩條路徑可以互相到達。圖的連通
性不會任何一個頂點的影響。這個性質具有許多重要的應用價值,例如現實中的通訊網絡部署,
出于可靠性和容錯性的考慮,在結構上應考慮多連通性,盡量避免割點的存在。這樣就算一個
通信節點損毀,也不會對其他節點的通信造成影響。
    無向圖的極大雙連通子圖被稱為2-連通分量。一個無向圖都具有一個或多個2-連通分量。
如果圖本身是一個雙連通圖,那么它本身是自己唯一的2-連通分量。一個無向圖具有2個或以
上2分量時,不難看出它的任意兩個2分量最多只可能有一個公共頂點。因為如果有多于一個公
共頂點,就可以證明這兩個2分量實際上可以組成一個更大的2分量,從而引起矛盾。進一步還
可以得出同一條邊不可能處于多個二分量之中,因為一條邊有兩個頂點,如果一條邊屬于多個
二分量,則相當于兩個頂點可以同時處于多個二分量之中,這與前述矛盾。
    綜上,所有二分量實際上把圖劃分為了不相交的子集,連接不同二分量的邊成為割邊。
   
    可以利用深度優先搜索求2-連通分量。如果生成樹的root是割點,當且僅當它有多于一個
子女。如果生成樹的非根節點是割點,當且僅當它沒有一個后代可以通過后向邊回到它的祖先。
根據這些條件,我們定義一個點的時間戳為深度優先數,代表著頂點在深度優先搜索時被訪問
的先后次序,記為D。如果D(i)<D(j),表明i點在serch過程中先于j點被訪問。為了比較方便的
知道一個頂點是不是割點,對頂點定義參數low,low[i]為從i或其后代出發,通過后向邊所能達
到的最小深度優先數。
    low[i]=min{ D(i) , min{low[j]|j為i的子女} , min{D(k)|(i,k)為后向邊} }

    
//edge為無向圖邊表,n為頂點數, e總邊數
    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為目前深度優先數
    
// 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];
           
                
// 無后向邊,分量結束
                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已經被訪問過,并且不等于父頂點v,證明有后向邊更新low
                    low[u] = ( low[u] < D[l->dest] ) ? low[u] : D[l->dest];
                }

            l
=l->next;
        }

       
    }