# 連通塊 Connected Component
此章節接續 [DFS 與 BFS](https://hackmd.io/@ShanC/bfs_dfs)、[併查集](https://hackmd.io/@ShanC/dsu)，要來聊聊該如何使用先前的內容來找連通塊
**本篇的圖皆為 undirected simple graph**

## 連通性 Connectivity
關於一張圖的連通性，有以下定義:
設有一張圖 $G$
- 假如 $G$ 是「連通的」，那 $G$ 就必存在一條 $(u, v)$ 路徑，否則就是「不連通的」
- 假如 $G$ 有一條 $(u, v)$ 路徑，則 $u$ 與 $v$ 「連通」
- 假如有一條 $(u,v)$ 邊，則 $u$ 與 $v$ 「相鄰」

graph hierarchy {
    node [shape="circle"]
    layout=fdp
    size = "4,3"
    a -- b
    a -- c
    c -- b
    d -- e
}

以上圖為例，$a$ 與 $c$ 連通，但 $b$ 與 $e$ 不連通；$a$ 與 $c$ 連通，因此存在至少一條路徑

## 連通塊 Connected Component
### 連通塊定義 The Definition of Connected Component
連通塊又稱連通分量、連通單元、連通成分，定義如下:

- 設一張圖 $G$，其連通塊為 $G$ 的極大 (maximal) 連通子圖 (subgraph)
- 若有一連通塊無邊 (即只有 $1$ 節點)，則稱為顯然的 (trivial) 連通塊
- 若有一連通塊有邊，則稱為非顯然的 (nontrivial) 連通塊
- 若 $G$ 只有一個連通塊，則稱 $G$ 為連通圖

以下圖來說，有兩個連通塊 $\{a,b,c,d,e\}$ 與 $\{f\}$，其中 $\{f\}$ 為顯然連通塊

<center>
<img src="https://hackmd.io/_uploads/r1MdoWiQkg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

### 性質: 連通塊的數量關係
#### 引理
假設 $G$ 有多個連通塊，每增加一條邊，則會減少 $0$ 或 $1$ 個連通塊；每減少一條邊則有可能增加 $0$ 或 $1$ 個連通塊

#### 定理
設一張圖 $G$ 有 $n$ 個節點與 $k$ 條邊，則 $G$ 最少有 $n - k$ 個連通塊

#### 證明
令 $G$ 有 $n$ 個節點與 $0$ 條邊，則 $G$ 有 $n$ 個連通塊。根據引理，每次加一條邊，最多可能減少 $1$ 個連通塊。因此設有 $k$ 條邊，則最少會有 $n - k$ 個連通塊

### 備註
當 $k=n-1$ 時，$G$ 最少會有 $1$ 個連通塊。又根據連通性，$G$ 只有 $1$ 連通塊時，$G$ 為一張連通圖。因此如果 $G$ 是一張連通圖，則至少有 $n-1$ 條邊

## 程式實作
### DFS 版本
#### 性質
1. 設 $C$ 與 $C'$ 為 $G$ 裡的連通塊，其中兩節點 $u \in V(C)$、$v \in V(C')$。如果存在 $(u, v)$ 路徑，則 $C$ 與 $C'$ 為相同的連通塊
2. 假設 $(u,v) \in E(G)$，使用 DFS 走訪 $G$ 時，如果能走訪到 $u$， 就必走訪到 $v$

BFS 也符合性質 2. ，所以也可以用來尋找連通塊，~~但是作者懶得寫~~

#### 程式碼
為了區分連通塊，我們可以將其編號，首先找到的為 $1$ 號，以此類推
- $id[i]$ : 第 $i$ 個節點所在的連通塊編號
- $sz[i]$ : 第 $i$ 個節點所在的連通塊大小
- $g[i]$ : 鄰接陣列，第 $i$ 個節點的鄰居
- $n$ : 節點數量

vector<int> g[MXN];
int id[MXN], sz[MXN], n;

void dfs(int u, int k) {
    sz[k]++, id[u] = k;
    for (int &v : g[u]) {
        if (id[v] == 0)
            dfs(v, k);
    }
}
int find_cc() {
    int cnt_cc = 0;                 // 紀錄連通塊數量
    for (int i = 1; i <= n; i++) {  // 1-based
        if (id[i] == 0)             // id[i] == 0 代表尚未走訪
            dfs(i, ++cnt_cc);
    }
    return cnt_cc;
}

#### 時間複雜度
$O(m + n)$， 與 DFS 相同

### 併查集實作
#### 性質
併查集的原理與連通性有相似之處，因此可以併查集維護節點的集合 $V$
關於併查集的原理可以看看[這篇](https://hackmd.io/@ShanC/dsu)

#### 程式碼
執行步驟如下:
1. 初始化併查集，將每個節點視為獨立的集合 (因為不知道是否連邊)
2. 對於所有邊 $(u,v)$，將每條邊的終點 $u$ 與 $v$ 合併為同一集合
3. 利用 $find()$ 函數尋找有幾個不同的根 (即集合代表)

int f[MAXN], sz[MAXN];
void init(int n) {                  // 初始化
    for (int i = 1; i <= n; i++) {  // 1-based
        f[i] = i;
        sz[i] = 1;
    }
}

int find(int x) {
    if (f[x] == x)  // 如果當前節點為 f[x] == x
        return x;   // 則為根節點
    f[x] = find(f[x]);
    return f[x];
}

void merge(int x, int y) {  // 將 x 和 y 合併
    x = find(x), y = find(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])  // 將小的併入大的
        swap(x, y);
    sz[x] += sz[y];
    f[y] = x;
}

int n;                // 節點數
vector<int> g[MAXN];  // 鄰接陣列

void find_cc() {
    vector<bool> vis(n + 5, false);
    init(n);
    int ret = 0;

    for (int i = 1; i <= n; i++) {  // 尋找所有連邊關係
        for (int &j : g[i])
            merge(i, j);
    }

    for (int i = 1; i <= n; i++)  // 1-based
        vis[find(i)] = true;
    for (int i = 1; i <= n; i++)  // 遍歷所有集合代表
        ret += vis[i];

    return ret;
}

#### 時間複雜度
- 初始化併查集: $O(n)$
- 尋找所有邊 + 合併: $O(m) \times O(\alpha(n))\approx O(m)$
- 遍歷節點找根: $O(\alpha(n))\times O(n) + O(n)\approx O(n)$
總時間複雜度: $O(m+n)$

## 題目練習
[Zerojudge f670. FJCU_109_Winter_Day1_Lab5 連通塊數量](https://zerojudge.tw/ShowProblem?problemid=f670)
[Zerojudge f260. 愛八卦的同學](https://zerojudge.tw/ShowProblem?problemid=f260)
[Zerojudge f680. 色塊數量](https://zerojudge.tw/ShowProblem?problemid=f680)
[Zerojudge a445. 新手訓練系列- 我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445)
[OnlineJudge-459 Graph Connectivity](https://vjudge.net/problem/UVA-459)
[CF contest-2034 C. Trapped in the Witch's Labyrinth](https://codeforces.com/contest/2034/problem/C)
[AtCoder abl_c Connect Cities](https://atcoder.jp/contests/abl/tasks/abl_c?lang=en)
[CSES Counting Rooms](https://cses.fi/problemset/task/1192)
[Zerojudge m372. APCS 3. 搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
[Zerojudge o927. 鐵路 (Rail)](https://zerojudge.tw/ShowProblem?problemid=o927)
[Zerojudge g598. APCS 4. 真假子圖](https://zerojudge.tw/ShowProblem?problemid=g598)

----

## 參考資料
- Introduction To Graph Theory - D. B. West
- Introduction to Algorithms, Fourth Edition
- [SA 流 C++ 競程修練心法](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FSyceyXTDE)
- [海大競程 併查集](https://hackmd.io/@LeeShoWhaodian/dsu#/2/33)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2024/12/2