---
tags: 成大高階競技程式設計 2021
---

# 2021 Week12 - Graph (BCC, SCC, LCA)

註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。

---

### 無向圖

* 連通圖（connected graph）
* 任意二點 $u, v$，都有從 $u$ 到 $v$ 的路徑的圖
* 連通分量（connected component）
* 極大的（maximal）連通子圖（subgraph）

<hr class="thin">

* 雙連通圖（biconnected graph）
* 移除任何一個點，圖還是連通的圖
* 雙連通分量（biconnected component）
* 極大的雙連通子圖

<hr class="dotted">

### 有向圖

* 強連通圖（strongly connected graph）
* 任意二點 $u, v$ 都有從 $u$ 到 $v$ 的路徑的圖（當然也有從 $v$ 到 $u$ 的路徑）
* 強連通分量（strongly connected component）
* 極大的強連通子圖

<hr class="dotted">

### DFS tree

一條邊 $(u,v)$ 的種類是

* tree edge
* DFS 時走過的邊
* back edge
* $v$ 是 $u$ 的祖先（且 $(u,v)$ 不是 tree edge）
* forward edge
* $v$ 是 $u$ 的子孫（且 $(u,v)$ 不是 tree edge）
* cross edge
* 其他

digraph {
    A [label="A"];
    B [label="B"];
    C [label="C"];
    D [label="D"];
    E [label="E"];
    F [label="F"];
    G [label="G"];
    H [label="H"];
    
    A -> B;
    B -> C;
    C -> D;
    D :e -> B [style=dashed, label="back"];
    A -> E;
    E -> F;
    F -> G;
    A :e -> G [style=tapered, label="forward"];
    A :se -> H;
    H :w -> F :e [style=dotted, label="cross"];
}

> **無向圖的邊只視為 tree edge 或 back edge**

---

# 關節點（AP, articulation point, cut vertex）

> 這裡只考慮無向圖

> articulation 也是連接的意思。

**一個點如果被移除，連通分量會增加的話，就稱為關節點。**

graph {
    rankdir=LR;
    
    A [label="A"];
    B [label="B", style=filled, fillcolor="red"];
    C [label="C"];
    D [label="D", style=filled, fillcolor="red"];
    E [label="E"];
    F [label="F"];
    
    A -- B;
    B -- C;
    C -- D;
    D :ne -- B :nw;
    D -- E;
    E -- F;
    F :se -- D :sw;
}

<hr class="thin">

在 DFS tree 上，一個節點 $u$ 與其子節點 $v$，
如果 $v$ 存在另一條不通過 $u$ 的路徑，可以到達 $u$ 的祖先，
這樣移除 $u$ 之後，子樹 $v$ [^subtree] 也不會變為新的連通分量；
反之，移除 $u$ 之後，子樹 $v$ 就會形成新的連通分量。

但有個特例是樹根，樹根沒有祖先，而因為無向圖沒有 cross edge，
不同子樹之間一定要通過樹根才能相連，所以樹根是不是關節點，
只需要看子樹數量是否大於 $1$。

> $v$ 要不通過 $u$ 而到達 $u$ 的祖先，就只能先往 $v$ 的子孫走，
> 再經過 back edge；
> 另一種理解方式是，因為子樹 $v$ 本身是連通的，
> 所以 $v$ 或 $v$ 的子孫要有一個鄰居是 $u$ 的祖先，
>這樣 $u$ 被移除後，子樹 $v$ 與 $u$ 的祖先還是連通的。

定義 $dep(u)$ 為 $u$ 的深度。
定義 $low(v)$ 為 $v$ 先往子孫走，再通過不超過一次的 back edge，
所能達到的節點的最小深度；
換句話說，就是 $v$ 與 $v$ 的子孫節點的「鄰居」中，節點的最小深度。

void dfs(int u, int w = -1) {
    int child{0};
    low[u] = dep[u] = ++d;
    for (auto& v : adj[u]) {
        if (v == w) continue;
        if (!dep[v]) { // tree edge
            ++child;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dep[u]) ap[u] = true;
        } else low[u] = min(low[u], dep[v]); // back edge
    }
    if (w == -1) ap[u] = (child > 1); // root
    --d;
}

> 為什麼不定義成可以通過好幾次 back edge 呢？
> 因為我們會考慮子樹 $v$ 所有的點，
> 如果通過 back edge 是到子樹中其他點的話，是沒有意義的；
> 如果通過 back edge 已經到了 $u$ 的祖先的話，那也足夠判斷了。
>
> > 而通過多個 back edge 可能出錯，如下圖的情況。
>
> ```graphviz
> digraph {
>
> A -> B;
> B -> C;
> C -> D;
> D :e -> B [style=dashed, label="back"];
> B :e -> A [style=dashed, label="back"];
> B -> E;
> E -> F;
> F -> G;
> E :ne -> A :se [style=dashed, label="back"];
> G :ne -> E :se [style=dashed, label="back"];
> }
> ```
>
> > 我們可能會以為 $C$ 可以通過 $D$ 到 $A$，
> > 但其實還是要通過 $B$，所以 $B$ 也還是關節點。

<hr class="dashed">

# 橋（bridge）

**一條邊如果被移除，連通分量會增加的話，就被稱為橋。**

graph {
    rankdir=LR;
    
    A [label="A"];
    B [label="B"];
    C [label="C"];
    D [label="D"];
    E [label="E"];
    F [label="F"];
    
    A -- B;
    B -- C;
    C -- D [color="red"];
    C :ne -- A :nw;
    D -- E;
    E -- F;
    F :se -- D :sw;
}

跟找關節點很像，如果 $low(v)\gt dep(u)$，
代表子樹 $v$ 沒有其他路徑，可以到達 $u$ 或 $u$ 的祖先，
移除 $(u,v)$ 的話，子樹 $v$ 就會形成新的連通分量。

void dfs(int u, int w = -1) {
    low[u] = dep[u] = ++d;
    for (auto& v : adj[u]) {
        if (v == w) continue;
        if (!dep[v]) { // tree edge
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dep[u]) bridge.emplace_back(u, v);
        } else low[u] = min(low[u], dep[v]); // back edge
    }
    --d;
}

<hr class="dashed">

# 雙連通分量（BCC, biconnected component）

**移除任何一個點，子圖還是連通的，也就是說沒有關節點。**

那一個圖分成雙連通分量會長怎麼樣呢？關節點一樣可以存在某些分量當中，
但如果是在關節點移除後，會不連通的部分，就要在不同的分量中，
這樣關節點移除的話，同一個雙連通分量中，點之間才不會被分開。

[^wikiBCC]

一樣先把關節點找出來，遇到關節點時就把圖拆成不同的分量。

> 樹根的 `low[v] >= dep[u]` 一定成立，
> 等於說每棵子樹都會拆成一個雙連通分量。
> （所以不管樹根是不是關節點，都是正確的。）

> 如果 `dep[v] >= dep[u]`，代表它是 back edge $(v,u)$，所以就不要管它。
>
> > **$v$ 是 $u$ 的子孫**，$(u,v)$ 其實是 forward edge 的概念，
> > 只是在無向圖中，$(u,v)$ 與 $(v,u)$ 是同一條邊，視為 back edge。

class BCC {
    int d;
    vector<int> dep{}, low{};
    vector<int> bccno{};
    vector<vector<int>> bcc{};
    stack<pair<int, int>> s{};
    void dfs(const vector<vector<int>>& adj, int u, int w = -1) {
        low[u] = dep[u] = ++d;
        for (auto& v : adj[u]) {
            if (v == w || dep[v] >= dep[u]) continue;
            if (!dep[v]) { // tree edge
                s.emplace(u, v);
                dfs(adj, v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] >= dep[u]) {
                    bcc.emplace_back();
                    while (true) {
                        auto [x, y]{s.top()};
                        s.pop();
                        if (bccno[x] != bcc.size()) bcc.back().push_back(x), bccno[x] = bcc.size();
                        if (bccno[y] != bcc.size()) bcc.back().push_back(y), bccno[y] = bcc.size();
                        if (x == u && y == v) break;
                    }
                }
            } else low[u] = min(low[u], dep[v]); // back edge
        }
        --d;
    }
public:
    vector<vector<int>> operator()(const vector<vector<int>>& adj) {
        int n{adj.size()};
        dep.assign(n, 0), low.resize(n), bccno.assign(n, 0);
        for (int i{0}; i < n; ++i) if (!dep[i]) dfs(adj, i);
        return move(bcc);
    }
};

> 此演算法由 John Hopcroft & Robert Tarjan 提出，並無正式名稱。

---

# 強連通分量（SCC, strongly connected component）

digraph {
    rankdir=LR;
    node [label=""];
    A, B, C, D, E [color=red];
    F [color=green];
    G, H, I, J [color=purple];
    A -> B;
    B -> C;
    C -> A;
    C -> D [dir=back];
    D -> E [dir=back];
    E -> C [dir=back];
    F -> C [dir=back];
    F -> E [dir=back];
    F -> G;
    E -> G;
    G -> H;
    G -> H [dir=back];
    H -> I [dir=back];
    J -> I;
    G -> J;
    J -> H;
}

### Tarjan's strongly connected components algorithm

> 跟找雙連通分量很像。

定義 $dfn(v)$ 為 $v$ 被拜訪的順序。
定義 $low(v)$ 為子樹 $v$ 與它們的強連通「鄰居」中，最早被拜訪的節點的順序。

不管 DFS 從誰開始，每個強連通分量總會有第一個被拜訪的點 $w$，使得 `low[w] == dfn[w]`；
除此之外，對於每個點 $v$，子樹 $v$ 總要有一個強連通鄰居比 $v$ 更早被拜訪，所以 `low[v] < dfn[v]`；
因此我們只需要找出 $w$，其他同個強連通分量中的點，一定是 $w$ 的子孫。

我們一樣用一個堆疊來記錄經過的點，當我們找到一個 $w$ （`low[w] == dfn[w]` 的節點）時，
堆疊中在 $w$ 之上的點就是一個強連通分量，我們就可以把這個強連通分量從堆疊中取出。

> 而當節點被拜訪完畢，卻還被留在堆疊中，代表 `low[v] < dfn[v]`，
> 也就是它可以到某個堆疊中更底下的點。

<hr class="thin">

強連通鄰居的話，就只能透過 back edge 或 cross edge 相連。

> **不是所有的 cross edge 都可以，要看彼此之間有沒有強連通。**
> 而所有的 back edge 一定可以，因為彼此之間一定是強連通的。

通過某個 cross edge $(v,u)$，如果 $u$ 還不在某個已知的強連通分量當中，
也就是說它還在堆疊中，這代表 $u$ 可以到 $lca(u,v)$，這也代表 $v$ 也可以到 $lca(u,v)$，
所以 $v$ 與 $lca(u,v)$ 也是強連通的（當然 $v$ 與 $u$ 就是強連通的）。

digraph {
    A [label="A,1"];
    B [label="B,2"];
    C [label="C,3"];
    D [label="D,4"];
    E [label="E,5"];
    F [label="F,6"];
    G [label="G,7"];
    
    A -> B;
    B -> C;
    C -> D;
    D -> C [style=dashed];
    C -> A [style=dashed];
    A -> E;
    E -> F;
    F -> G;
    G -> E [style=dashed];
    F -> C :e [style=dotted, fillcolor="red", color="red"];
}

> 所以當我們找到某個強連通分量中，第一個被拜訪的點 $w$，並拜訪完後，
> 堆疊中在它之上的任意點 $v$，都可以通過多個點，最終到達 $w$，
> 又因為這些點都是 $w$ 的子孫，所以都與 $w$ 是強連通的。
>
> > 為什麼說這樣就已經是極大的強連通子圖了呢？
> > 因為還沒被拜訪的節點，代表這邊到它們沒有路徑；
> > 已經被拜訪的子孫節點，卻已經被從堆疊中拿出的，代表它們到這邊沒有路徑；
> > cross edge 到其他強連通分量中的點（也是已經被從堆疊中拿出的），
> > 代表它們到這邊也沒有路徑；所以不會有任何點可以再擴大這個強連通子圖了。

class SCC {
    int d;
    vector<int> dfn{}, low{};
    vector<int> sccno{};
    vector<vector<int>> scc{};
    stack<int> s{};
    void dfs(const vector<vector<int>>& adj, int u) {
        low[u] = dfn[u] = ++d;
        s.emplace(u);
        for (auto& v : adj[u]) {
            if (sccno[v]) continue; // cross edge
            if (!dfn[v]) { // tree edge
                dfs(adj, v);
                low[u] = min(low[u], low[v]);
            } else low[u] = min(low[u], dfn[v]); // forward / back / cross edge
        }
        if (low[u] == dfn[u]) { // first vertex of a scc
            scc.emplace_back();
            while (true) {
                int x{s.top()}; s.pop();
                sccno[x] = scc.size(), scc.back().push_back(x);
                if (x == u) break;
            }
        }
    }
public:
    vector<vector<int>> operator()(const vector<vector<int>>& adj) {
        int n{adj.size()};
        d = 0, dfn.assign(n, 0), low.resize(n), sccno.assign(n, 0);
        for (int i{0}; i < n; ++i) if (!dfn[i]) dfs(adj, i);
        return move(scc);
    }
};

> 因為無向圖找 BCC 時，不會有 cross edge，
> 不管用 $dep$ 或 $dfn$ 都可以，只要父節點與子節點的大小關係正確就好。
> 但是有向圖找 SCC 的時候不一樣，只能用 $dfn(v)$，不然這個方法會行不通。

---

# 最低共同祖先（LCA, lowest common ancestor）

> **lowest 在這邊是 deepest（也可當作地位最低的）**；
> 上面的 low 則是指數字小的。

LCA 是指，一棵樹上的共同祖先中，深度最大的，也就是最靠近的那個共同祖先。

digraph {
    A [label="A"];
    B [label="B", style=filled, fillcolor=dimgray];
    C [label="C", style=filled, fillcolor=lightgray];
    D [label="D"];
    E [label="E", style=filled, fillcolor=lightgray];
    F [label="F"];
    
    A -> B;
    B -> C;
    B -> D;
    D -> E;
    A -> F;
}

> $C$ 與 $E$ 的 LCA 是 $B$。

假設樹一樣存在鄰接陣列，並已知樹根，
並另外紀錄 $d$ 陣列，代表節點深度。

> 樹根的深度（depth）為 $0$。

要找 $lca(u, v)$，最簡單的方法就是，先從 $u$ 往上走到樹根，
接下來從 $v$ 也往上走到樹根，第一個遇到 $u$ 也走過的節點就是了，
複雜度 $O(H)$。（$H$ 為樹高）

<hr class="dashed">

## pointer jumping technique (binary lifting)

我們先把剛剛的暴力解轉換一下，不失一般性的假設 $d(u)\le d(v)$，
我們先從 $v$ 往上走到與 $u$ 同高度，接著 $u, v$ 再一起往上走，直到交會為止。

1. $v$ 往上走 $d(v)-d(u)$ 步
2. $u, v$ 往上走 $d(lca(u,v))-d(v)$ 步

這邊問題就可以轉化為二個步驟，而且都有明確的起點與距離。

接著我們可以用類似二分搜的概念來加速，假設樹高小於 $32$，
我們先看距離有沒有超過 $16$，有的話就往上走 $16$ 步；
剩下的距離一定小於 $16$，我們再看它有沒有超過 $8$；
以此類推，$4,\ 2,\ 1$，就到終點了。

> 雖然不知道 $d(lca(u,v))-d(v)$ 到底是多長，
> 可是透過 $u,v$ 分別走某個距離到達的點，
> 就可以判斷是否已經走到或超過 $lca(u,v)$ 了。

定義 $an[u][i]$ 為 $u$ 往上走 $2^i$ 步到達的祖先。

> 如果超過樹根則設為 $-1$。

class LCA {
    const vector<vector<int>>& adj;
    int n;
    vector<int> d;
    vector<int> log2;
    vector<vector<int>> an{};
    void dfs(int u, int w = -1, int dep = 0) {
        d[u] = dep;
        an[u][0] = w;
        for (int i{1}; i <= log2[n - 1] && an[u][i - 1] != -1; ++i)
            an[u][i] = an[an[u][i - 1]][i - 1]; // 走 2^(i-1) 再走 2^(i-1) 步
        
        // 因為計算 an 會用到祖先的資訊，所以先計算再繼續往下
        for (auto& v : adj[u]) {
            if (v == w) continue; // parent
            dfs(v, u, dep + 1);
        }
    }
public:
    LCA(const vector<vector<int>>& _adj, int root)
    : adj{_adj}, n{adj.size()}, d(n), log2(n) {
        log2[1] = 0;
        for (int i{2}; i < log2.size(); ++i) log2[i] = log2[i / 2] + 1;
        an.assign(n, vector<int>(log2[n - 1] + 1, -1));
        dfs(root);
    }
    int operator()(int u, int v) {
        if (d[u] > d[v]) swap(u, v);

        for (int i{log2[d[v] - d[u]]}; i >= 0; --i)
            if (d[v] - d[u] >= (1 << i)) v = an[v][i];
        // v 先走到跟 u 同高度
        if (u == v) return u;
    
        for (int i{log2[d[u]]}; i >= 0; --i)
            if (an[u][i] != an[v][i]) u = an[u][i], v = an[v][i];
        // u, v 一起走到 lca(u, v) 的下方

        return an[u][0];
        // 回傳 lca(u, v)
    }
};

> 這裡初始化 `an`，複雜度就要 $O(|V|\log |V|)$，
> 其實可以先算出樹高，不要直接用到最大可能的樹高 $n-1$，
> 甚至可以每個 `an[u]` 依照 $u$ 的深度開不同長度，
> 但是複雜度還是一樣，常數比較小而已。

前處理複雜度 $O(|V|\log H)$。

<hr class="thin">

> 如果 $u$ 往上走 $2^i$ 步超過樹根，就讓 $an[u][i]$ 等於 $-1$。

查詢複雜度 $O(\log H)$。

> 因為我們沒有辦法區別 $lca(u,v)$ 與它的祖先，
> 所以我們先走到 lca(u, v) 的下方，最後再回傳它的父節點（`an[u][0]`）。

<hr class="dashed">

## Tarjan's offline LCAs algorithm

> offline algorithm 代表一開始就要知道所有的問題（有哪些 $lca(u,v)$），
> 不然就得把全部 $O(|V|^2)$ 個問題答案算好。

假設二點 $u,v$，$v$ 比 $u$ 先被拜訪到，而當拜訪到 $u$ 時，有以下的結論：

> **以下討論都是基於 DFS 剛拜訪到 $u$ 時的狀態**

如果 $v$ 不是 $u$ 的祖先，$v$ 一定處於拜訪完的狀態，
從 $v$ 往上找，第一個處於拜訪中的節點，就是 $lca(u,v)$。

我們還可以發現，$v$ 周圍拜訪完的任意節點 $w$，$lca(u,w)=lca(u,v)$，
而這些節點會形成一棵 $lca(u,v)$ 的子樹[^subtree2]。

> 若 $v$ 是 $u$ 的祖先，那就更簡單了，$lca(u,v)=v$。

只有那些拜訪中的節點是 $u$ 的祖先，也只有這些點有可能是 $lca(u,v)$，
所以對於其中某個節點 $x$，令 $x$ 與 $x$ 所有拜訪完畢的子樹所形成的集合為 $S$，
則對於 $S$ 中的任意一點 $v$，都會使得 $lca(u,v)=x$；
我們要做的就是當每棵子樹被拜訪完畢時，把它與父節點進行合併，
而對於某個節點 $v$，$lca(u,v)$ 就是 $v$ 所在集合的 $x$。

> 另一種觀點，從某個點 $x$ 的角度來看，二個子孫節點 $u,v$，$lca(u,v)$ 是否是 $x$？
> 如果 $u,v$ 分屬於 $x$ 的二棵不同的子樹，則 $lca(u,v)=x$；
> 如果 $u,v$ 在 $x$ 的同一棵子樹，則 $lca(u,v)\neq x$。
>
> > 當然如果 $u$ 或 $v$ 等於 $x$，$lca(u,v)=x$。
>
> 當我們拜訪到 $u$ 時，如果 $v$ 所在的子樹已經拜訪完畢，
> 代表 $u,v$ 分屬於不同子樹，而 $lca(u,v)=x$，
> 因此我們把拜訪完畢的子樹與 $x$ 合併，代表這些節點與 $u$ 的 LCA 都是 $x$。

digraph {
    A [label="A", style=dashed];
    B [label="B", style=dashed];
    C [label="C"];
    D [label="D"];
    E [label="E", style="dashed, filled", fillcolor=dimgray];
    F [label="F"];
    G [label="G"];
    H [label="H(v)", style=filled, fillcolor=lightgray];
    I [label="I"];
    J [label="J", style=dashed];
    K [label="K(u)", style="dashed, filled", fillcolor=lightgray];
    L [label="L", style=dotted];
    M [label="M", style=dotted];
    N [label="N", style=dotted];
    O [label="O", style=dotted];
    P [label="P", style=dotted];
    
    A -> B;
    B -> C;
    C -> D;
    B -> E;
    E -> F;
    F -> G;
    F -> I;
    G -> H;
    E -> J;
    J -> K;
    K -> L;
    K -> M;
    J -> N;
    N -> O;
    A -> P;
}

因為每個 $x$ 形成的集合都是沒有交集的，我們可以用併查集來快速運算。

> 為了要進行 weighted union，額外開一個 $ancestor$ 陣列，
> 紀錄每個集合真正的樹根。

class LCA {
    DSU dsu{0};
    vector<bool> vis{};
    vector<int> ancestor{};
    vector<vector<int>> que{};
    vector<tuple<int, int, int>> ans{};
    void dfs(const vector<vector<pair<int, long long>>>& adj, int u) {
        for (auto& v : que[u])
            if (vis[v]) ans.emplace_back(u, v, ancestor[dsu.find(v)]);

        vis[u] = true;
        ancestor[dsu.find(u)] = u;
        for (auto& [v, _] : adj[u]) {
            if (vis[v]) continue;
            dfs(adj, v);
            dsu.unionn(u, v);
            ancestor[dsu.find(u)] = u;
        }
    }
public:
    vector<tuple<int, int, int>> operator()(const vector<vector<pair<int, long long>>>& adj, int root, vector<pair<int, int>>& query) {
        int n{adj.size()};
        que.assign(n, {});
        for (auto& [u, v] : query) que[u].push_back(v), que[v].push_back(u);

        dsu.reset(n), vis.assign(n, false), ancestor.resize(n);
        dfs(adj, root);
        return move(ans);
    }
};

複雜度 $O(|V|+P\cdot\alpha(|V|))$。

> $P$ 為問題數量。
> $\alpha()$ 是 inverse Ackermann function，
> 是個成長非常緩慢的函數，基本上可視為常數。

<hr class="dashed">

## Euler Tour Technique

> 歐拉行跡（euler trail）：剛好經過每個邊一次的行跡。

將樹看成有向圖，並且每條樹邊變為二條有向邊，於是樹就可以被表示成一個歐拉迴路。

> 這樣的表示法被稱為 Euler tour representation (ETR)。

digraph {
    A [label="A"];
    B [label="B", style=filled, fillcolor=dimgray];
    C [label="C", style=filled, fillcolor=lightgray];
    D [label="D"];
    E [label="E"];
    F [label="F"];
    G [label="G"];
    H [label="H"];
    I [label="I"];
    J [label="J", style=filled, fillcolor=lightgray];
    K [label="K"];
    
    A -> B;
    B -> A [style=tapered];
    B -> C;
    C -> B [color=red, style=tapered];
    C -> D [color=red];
    D -> C [color=red, style=tapered];
    C -> E [color=red];
    E -> C [color=red, style=tapered];
    B -> F [color=red];
    F -> B [color=red, style=tapered];
    F -> G [color=red];
    G -> F [color=red, style=tapered];
    G -> H [color=red];
    H -> G [color=red, style=tapered];
    B -> I [color=red];
    I -> B [style=tapered];
    I -> J [color=red];
    J -> I [style=tapered];
    A -> K;
    K -> A [style=tapered];
}

digraph {
    path [shape=none, label=
<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
  <TR>
    <TD BORDER="0">euler:  </TD>
    <TD WIDTH="20">..</TD>
    <TD WIDTH="20">C</TD>
    <TD WIDTH="20">D</TD>
    <TD WIDTH="20">C</TD>
    <TD WIDTH="20">E</TD>
    <TD WIDTH="20">C</TD>
    <TD WIDTH="20">B</TD>
    <TD WIDTH="20">F</TD>
    <TD WIDTH="20">G</TD>
    <TD WIDTH="20">H</TD>
    <TD WIDTH="20">G</TD>
    <TD WIDTH="20">F</TD>
    <TD WIDTH="20">B</TD>
    <TD WIDTH="20">I</TD>
    <TD WIDTH="20">..</TD>
  </TR>  <TR>
    <TD BORDER="0">depth:  </TD>
    <TD WIDTH="20">..</TD>
    <TD WIDTH="20">2</TD>
    <TD WIDTH="20">3</TD>
    <TD WIDTH="20">2</TD>
    <TD WIDTH="20">3</TD>
    <TD WIDTH="20">2</TD>
    <TD WIDTH="20">1</TD>
    <TD WIDTH="20">2</TD>
    <TD WIDTH="20">3</TD>
    <TD WIDTH="20">4</TD>
    <TD WIDTH="20">3</TD>
    <TD WIDTH="20">2</TD>
    <TD WIDTH="20">1</TD>
    <TD WIDTH="20">2</TD>
    <TD WIDTH="20">..</TD>
  </TR>
</TABLE>>
];
}

> 一樣不失一般性地假設 $v$ 先被拜訪，再來才是 $u$。

從第一次經過 $v$，到第一次經過 $u$，中間的路徑完全落在子樹 $lca(u,v)$ 中；
而因為 $u,v$ 分屬於 $lca(u,v)$ 不同的子樹，所以一定會經過 $lca(u,v)$。

而子樹 $lca(u,v)$ 中，深度最小的點自然就是 $lca(u,v)$，
於是要找 $lca(u,v)$，可以轉化為尋找，
**第一次經過 $v$ 到第一次經過 $u$ 路徑上「深度最小的點」**。

> 這是一個 RMQ 問題，不用支援修改，可以用**稀疏表（sparse table）**。

class LCA {
    const vector<vector<int>>& adj;
    int n;
    vector<int> d, first, euler{}, log2{};
    vector<vector<int>> st{};
    void dfs(int u, int w = -1, int dep = 0) {
        d[u] = dep;
        first[u] = euler.size();
        euler.push_back(u);
        for (auto& v : adj[u]) {
            if (v == w) continue;
            dfs(v, u, dep + 1);
            euler.push_back(u);
        }
    }
public:
    LCA(const vector<vector<int>>& _adj, int root) : adj{_adj}, n{adj.size()}, d(n), first(n) {
        dfs(root);
        
        int tn{euler.size()};
        log2.resize(tn + 1);
        log2[1] = 0;
        for (int i{2}; i <= tn; ++i) log2[i] = log2[i / 2] + 1;

        st.assign(tn, vector<int>(log2[tn] + 1));
        for (int i{tn - 1}; i >= 0; --i) {
            st[i][0] = euler[i];
            for (int j{1}; i + (1 << j) <= tn; ++j) {
                auto& x{st[i][j - 1]};
                auto& y{st[i + (1 << (j - 1))][j - 1]};
                st[i][j] = d[x] <= d[y] ? x : y;
            }
        }
    }
    int operator()(int u, int v) {
        int l{first[u]}, r{first[v]};
        if (l > r) swap(l, r);
        ++r; // make the interval left closed right open
        
        int j{log2[r - l]};
        auto& x{st[l][j]};
        auto& y{st[r - (1 << j)][j]};
        return d[x] <= d[y] ? x : y;
    }
};

前處理複雜度 $O(|V|\log |V|)$，詢問複雜度 $O(1)$。

> 或是用線段樹，可以達到 $O(|V|)$ 前處理，$O(\log |V|)$ 詢問。

<hr class="dashed">

## 樹鏈剖分（heavy-light decomposition）

graph {
    node [shape=circle, style=filled, label=""];
    
    node[fillcolor=orange];
    D;
    node[fillcolor=red];
    A; B; C; E; F;
    node[fillcolor=yellow];
    G;
    node[fillcolor=green];
    H; I; J;
    node[fillcolor=blue];
    K; L;
    node[fillcolor=indigo];
    M;
    node[fillcolor=purple];
    N;
    
    edge [style=bold];
    A -- B -- C -- E -- F;
    H -- I -- J;
    K -- L;
    edge [style=dotted];
    C -- D;
    B -- G;
    A -- H;
    A -- K;
    K -- M;
    K -- N;
}

樹鏈剖分是一個將樹分解為一堆路徑的技巧；
其精神在於「**重鏈輕剖**」，鏈結重的子樹，剖去輕的子樹。

對於每個節點 $u$，選擇一個子節點 $v$，子樹 $v$ 是所有子樹最重的（節點最多），
稱這樣的邊為重邊（heavy edge），其餘則為輕邊（light edge）；
每個非葉節點，都通過重邊與一個子節點相連，形成一堆由重邊組成的路徑（heavy path）。

對於二個節點 $u,v$，如果 $u,v$ 在不同的路徑上，
而 $v$ 所在的路徑起點 $s(v)$ 比 $s(u)$ 比較深，
有可能 $u$ 是 $s(v)$ 的祖先，也有可能 $u$ 跟 $s(v)$ 沒有關係，
但 $s(v)$ 不會是 $u$ 的祖先，所以 $lca(u,v)=lca(u,s(v))$；
如果 $u,v$ 在同個路徑上，而 $v$ 的深度比較深，則 $lca(u,v)=u$。

class LCA {
    const vector<vector<int>>& adj;
    int n;
    vector<int> pa, dep, heavy, head;
    // 父節點, 深度, 重邊, 路徑起點
    int heavy_light(int u, int w = -1, int d = 0) {
        pa[u] = w, dep[u] = d;
        int mx{0}, tot{1};
        for (auto& v : adj[u]) {
            if (v == w) continue;
            int sz{heavy_light(v, u, d + 1)};
            if (sz > mx) mx = sz, heavy[u] = v;
            tot += sz;
        }
        return tot;
    }
    void decompose(int u, int h) {
        head[u] = h;
        for (auto& v : adj[u]) {
            if (v == pa[u]) continue;
            if (v == heavy[u]) decompose(v, h);
            else decompose(v, v);
        }
    }
public:
    LCA(const vector<vector<int>>& _adj, int root) : adj{_adj}, n{adj.size()}, pa(n), dep(n), heavy(n), head(n) {
        // Heavy-Light Decomposition
        heavy_light(root);
        decompose(root, root);
    }
    int operator()(int u, int v) {
        while (head[u] != head[v]) {
            if (dep[head[u]] <= dep[head[v]]) v = pa[head[v]];
            else u = pa[head[u]];
        }
        return dep[u] <= dep[v] ? u : v;
    }
};

每次透過輕邊到別條路徑上，路徑起點從 $s$ 變為 $s'$，
子樹 $s'$ 至少是子樹 $s$ 的二倍重，所以至多 $O(\log_2n)$ 次到達根節點；
複雜度為 $O(\log n)$。

---

# References

* 演算法筆記 - [Component](http://web.ntnu.edu.tw/~algo/Component.html)
* Wikipedia - [Biconnected component](https://en.wikipedia.org/wiki/Biconnected_component)
* Wikipedia - [Tarjan's strongly connected components algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
* CP-Algorithms - [Lowest Common Ancestor - Tarjan’s off-line algorithm](https://cp-algorithms.com/graph/lca_tarjan.html)
* Wikipedia - [Euler tour technique](https://en.wikipedia.org/wiki/Euler_tour_technique)
* CP-Algorithms - [Heavy-light decomposition](https://cp-algorithms.com/graph/hld.html)

---

# 練習題

| Problem | Tags |
|:-:|:- |
| [Network](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=251) | `AP` |
| [Street Directions](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=551) | `bridge` |
| [Mining Your Own Business](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3136) | `BCC` |
| [Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree) | `LCA` |
| [血緣關係](https://zerojudge.tw/ShowProblem?problemid=d767) | `LCA` |

[^subtree]: **子樹 $v$ 代表以 $v$ 為樹根的子樹（subtree rooted at v）。**

[^subtree2]: **$u$ 的子樹代表以 $u$ 的子節點為樹根的子樹（subtree rooted at v, which is a child of u）。**

[^wikiBCC]: [Wikipedia File:Graph-Biconnected-Components.svg](https://en.wikipedia.org/wiki/File:Graph-Biconnected-Components.svg)

<style>

hr.thin {
height: 0.5px;
}

hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}

hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}

/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}

/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}

</style>