hiho圖的聯通性（自留）

無向圖割邊割點算法

而當(u,v)為樹邊且low[v]>dfn[u]時，表示v節點只能通過該邊(u,v)與u連通，那么(u,v)即為割邊。

void dfs(int u) {
    //記錄dfs遍歷次序
    static int counter = 0;    
    
    //記錄節點u的子樹數
    int children = 0;
    
    ArcNode *p = graph[u].firstArc;
    visit[u] = 1;

    //初始化dfn與low
    dfn[u] = low[u] = ++counter;

    for(; p != NULL; p = p->next) {
        int v = p->adjvex;
        
        //節點v未被訪問，則(u,v)為樹邊
        if(!visit[v]) {
            children++;
            parent[v] = u;
            dfs(v);

            low[u] = min(low[u], low[v]);

            //case (1)
            if(parent[u] == NIL && children > 1) {
                printf("articulation point: %d\n", u);
            }

            //case (2)
            if(parent[u] != NIL && low[v] >= dfn[u]) {
                printf("articulation point: %d\n", u);
            }
            
            //bridge
            if(low[v] > dfn[u]) {
                printf("bridge: %d %d\n", u, v);
            }
        }

        //節點v已訪問，則(u,v)為回邊
        else if(v != parent[u]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

?

邊雙聯通分量算法

對于一個無向圖的子圖，當刪除其中任意一個點后，不改變圖內點的連通性，這樣的子圖叫做點的雙連通子圖。而當子圖的邊數達到最大時，叫做點的雙連通分量。

直觀的做法自然先用上周的算法求出所有橋，去掉所有橋之后再做DFS求出每一個連通子圖。我們這周要介紹一種更"抽象"的算法，通過在Tarjan算法當中巧妙地用一個棧來統計出每一個組內的節點，其代碼如下：

void dfs(int u) {
    //記錄dfs遍歷次序
    static int counter = 0;    
    
    //記錄節點u的子樹數
    int children = 0;
    
    ArcNode *p = graph[u].firstArc;
    visit[u] = 1;

    //初始化dfn與low
    dfn[u] = low[u] = ++counter;
    
    //將u加入棧
    stack[++top] = u;

    for(; p != NULL; p = p->next) {
        int v = p->adjvex;
        
        //節點v未被訪問，則(u,v)為樹邊
        if(!visit[v]) {
            children++;
            parent[v] = u;
            dfs(v);

            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                printf("bridge: %d %d\n", u, v);    // 該邊是橋
                bridgeCnt++;  
            }
        }

        //節點v已訪問，則(u,v)為回邊
        else if(v != parent[u]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (low[u] == dfn[u])
    {
        // 因為low[u] == dfn[u]，對(parent[u],u)來說有dfn[u] > dfn[ parent[u] ]，因此low[u] > dfn[ parent[u] ]
        // 所以(parent[u],u)一定是一個橋，那么此時棧內在u之前入棧的點和u被該橋分割開
        // 則u和之后入棧的節點屬于同一個組
        將從u到棧頂所有的元素標記為一個組，并彈出這些元素。
    }
}

?

強連通分量

對于有向圖上的2個點a,b，若存在一條從a到b的路徑，也存在一條從b到a的路徑，那么稱a,b是強連通的。
對于有向圖上的一個子圖，若子圖內任意點對(a,b)都滿足強連通，則稱該子圖為強連通子圖。
非強連通圖有向圖的極大強連通子圖，稱為強連通分量。
特別地，和任何一個點都不強連通的單個點也是一個強連通分量。

tarjan(u)
{
    Dfn[u]=Low[u]=++Index                      // 為節點u設定次序編號和Low初值
    Stack.push(u)                              // 將節點u壓入棧中
    for each (u, v) in E                       // 枚舉每一條邊
        if (v is not visted)                   // 如果節點v未被訪問過
            tarjan(v)                          // 繼續向下找
            Low[u] = min(Low[u], Low[v])
        else if (v in Stack)                   // 如果節點v還在棧內(很重要,無向圖沒有這一步)
            Low[u] = min(Low[u], Dfn[v])
    if (Dfn[u] == Low[u])                      // 如果節點u是強連通分量的根
        repeat
            v = Stack.pop                      // 將v退棧，為該強連通分量中一個頂點
            mark v                             // 標記v，同樣通過棧來找連通分量
        until (u == v)
}

scc + 縮點 + topo

?

點的雙連通分量

對于一個無向圖的子圖，當刪除其中任意一個點后，不改變圖內點的連通性，這樣的子圖叫做點的雙連通子圖。而當子圖的邊數達到最大時，叫做點的雙連通分量。

???????????????????????????????????????

對于橋的兩種情況，它分割個區域數剛好就等于割點數+1；而連通分量內的割點同樣也是，每存在一個割點，點的雙連通分量就增加一個。

點的雙連通分量就等于割點數量加1。

每存在一個割點，就把一個區域一分為二，所以最后的結果也就是統計割點的數量就可以了。而對于分組具體情況，我們仍然采用棧來輔助我們記錄

void dfs(int u) {
    //記錄dfs遍歷次序
    static int counter = 0;    
    
    //記錄節點u的子樹數
    int children = 0;
    
    ArcNode *p = graph[u].firstArc;
    visit[u] = 1;

    //初始化dfn與low
    dfn[u] = low[u] = ++counter;

    for(; p != NULL; p = p->next) {
        int v = p->adjvex;
        if(edge(u,v)已經被標記) continue; 

        //節點v未被訪問，則(u,v)為樹邊
        if(!visit[v]) {
            children++;
            parent[v] = u;
            edgeStack[top++] = edge(u,v); // 將邊入棧
            dfs(v);
            
            low[u] = min(low[u], low[v]);

            //case (1)
            if(parent[u] == NIL && children > 1) {
                printf("articulation point: %d\n", u);
                // mark edge
                // 將邊出棧，直到當前邊出棧為止，這些邊標記為同一個組
                do {
                    nowEdge = edgeStack[top];
                    top--;
                    // 標記nowEdge
                }    while (nowEdge != edge(u,v))
            }

            //case (2)
            if(parent[u] != NIL && low[v] >= dfn[u]) {
                printf("articulation point: %d\n", u);
                // mark edge
                // 將邊出棧，直到當前邊出棧為止，這些邊標記為同一個組
                do {
                    nowEdge = edgeStack[top];
                    top--;
                    // 標記nowEdge
                }    while (nowEdge != edge(u,v))
            }
            
        }

        //節點v已訪問，則(u,v)為回邊
        else if(v != parent[u]) {
            edgeStack[top++] = edge(u,v);
            low[u] = min(low[u], dfn[v]);
        }
    }
}

?