# Connected Component (連通分量)
## DFS-Tree
### 定義
> 在 DFS 的過程中，紀錄走訪的節點與邊，形成一棵 **DFS-Tree**。
::: success
#### 有關邊的分類
Tree Edge : DFS 過程中實際走訪所形成的邊
| Back Edge | Forward Edge | Cross Edge |
| ---------------- | --------------- | --------------------- |
| 指向 DFS 樹中祖先節點的邊 | 指向已拜訪過的子孫節點（非直接子節點）的邊 | 指向其他子樹或已完成探索區域的邊 |
:::
### 定理 1
**對於無向連通圖** $G=(V,E)$，其 DFS-Tree 中**只會出現 Tree Edge 與 Back Edge**。
> **證明**：
> 假設 DFS-Tree 中出現 Cross Edge，則必須存在三個節點 $a,b,c$，使得 $a$ 是 $b,c$ 的祖先，且 $b,c$ 位於不同子樹，並且 $b,c$ 之間有一條邊（這條邊才會被歸類為 Cross Edge）。然而在 DFS 的過程中，當我們從 $a$ 拜訪 $b$ 時，由於 $b,c$ 之間存在邊，DFS 一定會從 $b$ 走到 $c$，使得 $c$ 成為 $b$ 的子孫。如此一來，該邊就會成為 Tree Edge 或 Back Edge，而非 Cross Edge。這與假設矛盾，因此無向連通圖中不會出現 Cross Edge（Forward Edge 同理）。
---
## AP 與 Bridge
### 定義
::: success
| AP (Articulation Point, 割點) | Bridge (橋) |
| --------------------------- | ----------------- |
| 從連通圖中移除此節點後，圖變得不連通 | 從連通圖中移除此邊後，圖變得不連通 |
* **$D(v)$**：節點 $v$ 在 DFS 過程中的時間戳（= DFS 深度），定義根節點 $D(root)=0$。
* **$L(v)$**：從節點 $v$ 與其子樹出發，**最多透過一條 Back Edge** 可以到達的節點的最小 DFS 深度（即 **low-link value**）。
**註** : 不難發現 $\forall$back edge $\not \in$ Bridge。
:::
### 定理 1
**若 DFS-Tree 的根節點 $r$ 有至少兩個子樹，則 $r$ 是 AP。**
> **證明**：
> 若 $deg(r) = 1$，刪除 $r$ 之後，DFS Tree 下方的子節點可以直接作為新根，圖仍連通。
> 但若 $deg(r) \ge 2$，刪除 $r$ 後，其下方的多個子樹將彼此斷開，形成多個連通分量，因此 $r$ 必為 AP。
---
### 定理 2
**對於 DFS-Tree 上的非根節點 $v$：**
$$
v \text{ 是 AP} \iff \exists w \text{ 是 } v \text{ 的子節點，使得 } L(w) \ge D(v)
$$
> **證明**：
> (⇒) 若 $v$ 是割點，則刪掉 $v$ 後，至少有一個子樹（以子節點 $w$ 為根）與圖的其他部分斷開。若該子樹存在 back edge 連回 $v$ 的祖先（即 $L(w) < D(v)$），即使刪除 $v$ 也能保持連通，與 $v$ 是割點的假設矛盾。因此必有子節點 $w$ 使 $L(w) \ge D(v)$。
>
> (⇐) 反之，若存在 $w$ 使 $L(w) \ge D(v)$，說明從 $w$ 的子樹中，沒有 back edge 可以連到 $v$ 的祖先。刪掉 $v$ 後，$w$ 的子樹就無法與圖上層連通，因此 $v$ 必為割點。
---
### 定理 3
$\text{let v DFS-Tree上一點}, (v, w) 為 bridge\iff \exists w \text{ 是 } v \text{ 的子節點，使得 } L(w)>D(v)$
> **證明**：
> 同上，因為沒有從 $w$ 的及其子樹出發的 back edge 可以連到 深度$<D(v)$的點，因此若邊 $(v, w)$ 是 bridge。
>
### 線性時間求圖上 AP/Bridge 的方法
結合上述定理可得此程式，看你需要對 AP/Bridge 來修改。
```cpp=
void dfs(int now, int par) {
dfn[now]=low[now]=ts++;
for(auto v:adj[now]) {
if(v==par) continue; //這邊如果是有邊權的情況再調整
if(!dfn[v]) {
dfs(v, now);
low[now]=min(low[now], low[v]);
}
else low[now]=min(low[now], dfn[v]);
}
// if(now != root && low[nb] >= dfn[now]) -> AP
// if(low[nb] > dfn[now]) -> bridge
// if(now == root && child >= 2) -> AP
}
```
## Bridge Connected Component
### 定義
::: success
將一張圖 $G(V, E)$，的所有的橋給移除，就會變成橋連通分量(又稱邊雙)。
* 橋連通分量 = Bridge Connected Component 簡稱 BCC。
* 性質 : 橋連通分量上的任何一條邊被移除都不會影響橋的連通性，且將原本的橋給放回去後，會變成一棵樹。
:::
### 定理 1
**若**$D(w)=L(w)$，則 $w$ 是橋連通分量上的一端點。
> **證明**：
>DFS 時，若某個點 沒辦法透過 Back Edge 回到祖先 (更淺的節點)，那麼 DFS Tree 上就會在這個點「切斷」。
實作
```cpp=
void dfs(int now, int par) {
dfn[now]=low[now]=ts++;
stk.push(now);
for(auto v:adj[now]) {
if(v==par) continue; //這邊如果是有邊權的情況再調整
if(!dfn[v]) {
dfs(v, now);
low[now]=min(low[now], low[v]);
}
else low[now]=min(low[now], dfn[v]);
}
if(low[now]==dfn[now]) { //註 1
int x;
bcccnt++;
do {
x=stk.top();
bcc[x]=bcccnt;
stk.pop();
} while(x!=now);
}
}
```
* 註 1
> 遍歷 $v$ 的子樹後，若 $v$ 的子樹沒辦法透過 Back Edge 回到 $v$ 的祖先，則 $v$ 為橋連通分量上的一端點，若 $v$ 的子樹中存在其他橋連通分量，則分量對在遞迴到它時，完成它在 stk 的移除，使 $v$ 的橋連通分量不包含它。
* 註 2
這是需要圖無重邊才能使用。若圖有重邊可能形成 $G$ 有兩個點兩條無向邊。使圖不存在 Bridge。
::: spoiler 如果題目有重邊可以點這裡
為了解決重邊，核心想法是在 DFS 過程中紀錄哪一條邊是橋。
```cpp=
//0-based 重邊
struct EdgeBCC{
int n, m, dep, sz;
vector<vector<pair<int, int>>> G;
vector<vector<int>> bcc;
vector<int> dfn, low, stk, isBridge, bccId;
vector<pair<int, int>> edge, bridge;
EdgeBCC(int _n) : n(_n), m(0), sz(0), dfn(n), low(n), G(n), bcc(n), bccId(n) {}
void add_edge(int u, int v) {
edge.push_back({u, v});
G[u].push_back({v, m});
G[v].push_back({u, m++});
}
void dfs(int now, int pre) {
dfn[now] = low[now] = ++dep;
stk.push_back(now);
for (auto [x, id] : G[now]){
if (!dfn[x]){
dfs(x, id);
low[now] = min(low[now], low[x]);
}else if (id!=pre){
low[now] = min(low[now], dfn[x]);
}
}
if (low[now]==dfn[now]){
if (pre!=-1) isBridge[pre] = true;
int u;
do{
u = stk.back();
stk.pop_back();
bcc[sz].push_back(u);
bccId[u] = sz;
} while (u!=now);
sz++;
}
}
void get_bcc() {
isBridge.assign(m, 0);
dep = 0;
for (int i=0 ; i<n ; i++){
if (!dfn[i]) dfs(i, -1);
}
for (int i=0 ; i<m ; i++){
if (isBridge[i]){
bridge.push_back({edge[i].first , edge[i].second});
}
}
}
};
```
:::
## Biconnected Component
### 定義
::: success
* 雙連通分量(點雙) = Biconnected Component 也是簡稱 BCC。
* 性質 : 若一張圖為雙連通則該圖不存在AP。
我們稱圖 $G=(V, E)$ 的雙連通分量 $S\subseteq V$ 滿足以下條件 :
1. $S$ 是雙連通的。
2. 無法再加一個點就無法滿足 1.
:::
接著以下圖舉例。
可以發現可以把此圖改成下面兩種的雙連通分量。
不難發現，如果一個點 $v$ 可以同時可能在兩個雙連通分量，那這個點就會是 $G$ 的 $AP$。
從上面我們知道 AP 即為連接不同雙連通分量的「端點」，
因此也能用類似的方式來求出雙連通分量。
不覺得這個跟判斷橋連通很像嗎?
所以我們按照橋連通來實作吧。
但重邊與否應該不影響這邊的實作。
```cpp=
struct BCC {
int n, timer;
vector<vector<int>> G;
vector<int> dfn, low;
vector<vector<int>> bcc;
stack<pair<int,int>> stk;
vector<bool> inBCC; // 標記哪些點出現在 BCC 中
vector<char> vis; // 用於 extractBCC，避免 sort/unique
BCC(int _n): n(_n), timer(0) {
G.assign(n, {});
dfn.assign(n, 0);
low.assign(n, 0);
inBCC.assign(n, false);
vis.assign(n, 0);
}
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int u, int parent) {
dfn[u] = low[u] = ++timer;
for (int v : G[u]) {
if (!dfn[v]) {
stk.emplace(u, v); // 樹邊
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) { // u 是關節點
extractBCC(u, v);
}
} else if (v != parent && dfn[v] < dfn[u]) {
stk.emplace(u, v); // 回邊
low[u] = min(low[u], dfn[v]);
}
}
}
void extractBCC(int u, int v) {
vector<int> comp;
while (!stk.empty()) {
auto [x, y] = stk.top(); stk.pop();
if (!vis[x]) { vis[x] = true; comp.push_back(x); }
if (!vis[y]) { vis[y] = true; comp.push_back(y); }
if (x == u && y == v) break;
}
if (!comp.empty()) {
for (int node : comp) {
inBCC[node] = true;
vis[node] = false; // reset for下一次 BCC 使用
}
bcc.push_back(comp);
}
}
void get_bcc() {
for (int i = 0; i < n; i++) {
if (!dfn[i]) {
dfs(i, -1);
if (!stk.empty()) {
vector<int> comp;
while (!stk.empty()) {
auto [x, y] = stk.top(); stk.pop();
if (!vis[x]) { vis[x] = true; comp.push_back(x); }
if (!vis[y]) { vis[y] = true; comp.push_back(y); }
}
if (!comp.empty()) {
for (int node : comp) {
inBCC[node] = true;
vis[node] = false;
}
bcc.push_back(comp);
}
}
}
}
// 單獨出現的點（沒在任何 BCC 中）
for (int i = 0; i < n; i++) {
if (!inBCC[i]) {
bcc.push_back({i});
}
}
}
};
```
Sign in with Wallet
Connect another wallet