---
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
* 其他
```graphviz
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 也是連接的意思。
**一個點如果被移除，連通分量會增加的話，就稱為關節點。**
```graphviz
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$ 的子孫節點的「鄰居」中，節點的最小深度。
```cpp!
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）
**一條邊如果被移除，連通分量會增加的話，就被稱為橋。**
```graphviz
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$ 就會形成新的連通分量。
```cpp!
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。
```cpp!
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）
```graphviz
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$ 就是強連通的）。
```graphviz
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 到其他強連通分量中的點（也是已經被從堆疊中拿出的），
> > 代表它們到這邊也沒有路徑；所以不會有任何點可以再擴大這個強連通子圖了。
```cpp!
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 是指，一棵樹上的共同祖先中，深度最大的，也就是最靠近的那個共同祖先。
```graphviz
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$。
```cpp!
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$。
```graphviz
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$ 陣列，
> 紀錄每個集合真正的樹根。
```cpp!
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)。
```graphviz
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];
}
```
```graphviz
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）**。
```cpp!
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）
```graphviz
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$。
```cpp!
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>
Sign in with Wallet
Connect another wallet