圖論 - HackMD

DFS-Tree & Tarjan Low Function

DFS Tree 顧名思義就是你先挑一個點當根來跑 DFS，然後 DFS 走到的邊我們就叫樹邊 (Tree Edge)，這棵樹就叫 DFS Tree，剩下的非樹邊會有三種狀況 :

Forward Edge 前向邊 : 邊 \(uv\)， \(v\) 是 \(u\) 的子樹
Back Edge 返祖邊 : 邊 \(uv\)， \(v\) 是 \(u\) 的祖先
Cross Edge 交錯邊 : 邊 \(uv\)，\(u,v\) 沒有祖孫關係

這時應該可以發現在無向圖上是不可能存在 Cross Edge 與 Forward Edge 的，有向圖上則都有可能出現。

我們定義一個點的 \(\text{dfn}(u)\) (又稱 dfs order) 是他是第幾個被 dfs 到的點 (也就是 dfs 前序編號)，定義 Tarjan low function \(\text{low}(u)\) 是所有 \(u\) 的子孫可以透過一條邊 (不論是否是 Tree Edge) 可以到的點的最小的 \(\text{dfn}\) ，也就是 \(\text{low}(u) = \min(\{\text{dfn}(x) | x \in \mathcal{N}(v), v \in \text{subtree}(u) - \{u\} \})\)。

這個東西的用途非常多，有趣的是當在無向圖上，我們只關心祖孫關係之間的 \(\text{low}\) 的相對關係時，\(\text{dfn}\) 可以用 \(\text{depth}\) 替代。

點雙連通分量 BCC-V (Bi-connected Component - Vertex)

定義

如果對於一個連通的點集 \(S\) 若移除任意一個元素 \(u\) 都還是連通，我們稱極大的這個點集 \(S\) 為一個點雙連通分量。

反之我們定義割點 (AP, Articulation Points) 為所以移除此點後圖就不連通的點。

性質

一個非 AP 最多只會在一個 BCC - V 內。
兩點 \(u,v\) 在同一個 BCC - V \(\iff\)移除非此兩點的任意點都無法使這兩點不連通
兩點 \(u,v\) 在同一個大於三個點的 BCC - V 中 \(\iff\) 存在一簡單環通過 \(u,v\)

兩點 \(u,v\) 在同一個 BCC - V 中 \(\iff\) 存在兩條除了端點外點互斥的路徑
三點 \(a\),\(b\),\(c\) 在同一個 BCC - V 中 \(\iff\)此三點任意順序都存在一簡單路徑依序過這三點
將每個 BCC - V 創一個虛點後，將 BCC - V 上的人連到這個虛點，這樣建出來的圖是一棵樹

怎麼找一個?

觀察到對於不是根的點 \(u\)，如果 \(\text{low}(u) \ge \text{dfn}(u)\) (可以用 depth 代替)，這個點很明顯是 AP，而且這個條件是若且唯若的，證明大概是因為拔掉 \(u\) 以後 \(u\) 的小孩與根的連通性就受上面那個條件決定了。

而對於根，如果只有一個子樹就不是 AP，否則就是。

實作 Code:

void Tarjan(int nd, int rt){
    been[nd] = 1;
    depth[nd] = depth[rt] + 1;
    low[nd] = depth[nd];
    
    dfs_stack.push_back(nd);

    int cnt = 0;

    bool flag = 0;

    for(auto i:graph[nd]){
        if(i == rt && !flag){
            flag = 1;
            continue;
        }
        if(been[i])
            low[nd] = min(low[nd], depth[i]);
        else{
            cnt++;
            Tarjan(i, nd);
            low[nd] = min(low[i], low[nd]);
            if(low[i] >= depth[nd]){
                BCC_ptr++;
                while(dfs_stack.back() != i){
                    BCC[BCC_ptr].push_back(dfs_stack.back());
                    dfs_stack.pop_back();
                }
                BCC[BCC_ptr].push_back(i);
                dfs_stack.pop_back();
                BCC[BCC_ptr].push_back(nd);
            }
        }
    }
    if(!cnt && rt == N + 1){
        BCC_ptr++;
        BCC[BCC_ptr].push_back(nd);
    }
    return;
}

這裡是用 depth 代替 dfn

時間複雜度 : \(O(\lvert V \rvert + \lvert E \rvert)\)

邊雙連通分量 BCC-E (Bi-connected Component - Edge)

定義

如果對於一個連通的點集 \(S\) 若移除任意一條邊 \(u\) 都還是連通，我們稱極大的這個點集 \(S\) 為一個邊雙連通分量。

反之我們定義橋 (Bridge) 為所以移除此邊後圖就不連通的邊。

性質

\(u,v\) 同在一個 BCC - V 內且此 BCC - V 有 3 個以上的點 \(\implies\) \(u,v\) 在同一個 BCC - E 內

下面的性質則與 BCC - V 大多相似，證明也類似 :

兩點 \(u,v\) 在同一個 BCC - E \(\iff\)移除任意邊都無法使這兩點不連通

任意非橋的邊存在一簡單環包含他
兩點 \(u,v\) 在同一個 BCC - E 中 \(\iff\) 存在兩條邊互斥的路徑
將每個 BCC - E 縮成一個虛點後，建出來的圖是一棵樹

怎麼找一個?

觀察到對於不是根的點 \(u\)，如果 \(\text{low}(u) = \text{dfn}(u)\) (可以用 depth 代替)，這個點很明顯是橋的下端點，而且這個條件是若且唯若的，證明大概是因為拔掉邊 \(u, \text{par}(u)\) 的小孩與根的連通性就受上面那個條件決定了。

實作大部分根 BCC - V 很像。
實作 Code:

void Tarjan(int nd, int rt){
    been[nd] = 1;
    depth[nd] = depth[rt] + 1;
    low[nd] = depth[nd];
    dfs_stack.push_back(nd);

    bool flag = 0;

    for(auto i:graph[nd]){
        if(!flag && i == rt)
            flag = 1;
        else if(been[i])
            low[nd] = min(low[nd], depth[i]);
        else{
            Tarjan(i, nd);
            low[nd] = min(low[nd], low[i]);
        }
    }

    if(low[nd] == depth[nd]){
        BCC_ptr++;
        while(dfs_stack.back() != nd){
            BCC[BCC_ptr].push_back(dfs_stack.back());
            dfs_stack.pop_back();
        }
        BCC[BCC_ptr].push_back(dfs_stack.back());
        dfs_stack.pop_back();
    }
    return;
}

這裡是用 depth 代替 dfn

強連通分量 SCC (Strongly Connected Component)

定義

如果對於一個點集 \(S\) 滿足任意兩元素 \(u,v\) 是互相 reachable 的，我們稱極大的這個點集 \(S\) 為一個強連通分量。

性質

將每個 SCC 縮起來後得到的圖會是 DAG，且每個 SCC 裡都有一個有向環
其他真的沒什麼好講的

怎麼找一個?

觀察到如果一個人已經離開了 dfs stack，那你跟他就沒有機會在同一個 SCC 內，所以我們只關心還在 dfs stack 內的人，而如果出現了 \(\text{low}(u) = \text{dfn}(u)\) 就代表現在在 stack 上的人是一個 SCC 了，注意這裡的 \(\text{dfn}\) 不能用 depth 代替，不然 cross edge 會出大事。

實做:

void Tarjan(int nd){
    dfn[nd] = ++now_dfn;
    low[nd] = dfn[nd];
    been[nd] = 1;
    in_stack[nd] = 1;
    dfs_stk.push_back(nd);

    for(auto i:graph[nd]){
        if(!been[i]){
            Tarjan(i);
            low[nd] = min(low[nd], low[i]);
        }
        else if (in_stack[i])
            low[nd] = min(low[nd], dfn[i]);
    }

    if(low[nd] == dfn[nd]){
        scc_amnt++;
        while(dfs_stk.back() != nd){
            in_stack[dfs_stk.back()] = 0;
            scc_num[dfs_stk.back()] = scc_amnt;
            dfs_stk.pop_back();
        }
        in_stack[dfs_stk.back()] = 0;
        scc_num[dfs_stk.back()] = scc_amnt;
        dfs_stk.pop_back();
    }
    return;
}

Kosaraju

Kosaraju 是一個實做簡單但正確性較 Tarjan 不直覺得 SCC 算法，實作是先在正圖上獲得 dfs 後序 (離開點的順序)，這跟拓排序十分相似，如果此圖是 DAG 的話就就是拓排序了，接著在依照這個順序的 reverse 在反圖上跑 dfs，每次 dfs 到的人就是同一個 SCC 內的了。

實作:

void dfs(int nd, bool is_rev){
    been[nd] = 1;
    for(auto i:graph[nd][is_rev]){
        if(!been[i])
            dfs(i, is_rev);
    }
    path[is_rev].push_back(nd);
}

void Kosaraju(int N){
    for (int i = 1; i <= N; i++){
        if(!been[i])
            dfs(i, 0);
    }
    been.reset();
    reverse(path[0].begin(), path[0].end());
    for(auto i:path[0]){
        if(!been[i]){
            dfs(i, 1);
            scc_amnt++;
            for(auto j:path[1]){
                scc_num[j] = scc_amnt;
            }
            path[1].clear();
        }
    }
    return;
}

時空都與 Tarjan 相同。

有趣的是，Kosaraju 幫 SCC 編號的順序是拓排序，Tarjan 是拓排逆序。

K 連通分量 (KCC - V / E)

顧名思義就是需要移除至少 K 個點 / 邊才能讓他不連通，要怎麼做呢?
跑 flow 找最小割就知道是幾連通了。

K = 3 的話是線性的，用某種魔改的 low 去找 cut pair
可以看看

題目

CSES - Coin Collector
CSES - Necessary Roads
CSES - Necessary Cities
TIOJ 1910
Library Checker - Strongly Connected Components
Library Checker - Two-Edge-Connected Components
Library Checker - Three-Edge-Connected Components
Library Checker - Biconnected Components