圖論經典：暢通工程 — 並查集/ DFS 求連通分量最少新建道路數

問題建模

給定 N 個城鎮（節點）和 M 條現有道路（無向邊），道路可能重複。目標：使任意兩城鎮連通（直接或間接）。**求最少還需建設多少條道路？**

數學轉化

• 將城鎮抽象為圖的頂點，道路為無向邊
• 「任意兩城鎮連通」 ⇔ 圖連通（只有一個連通分量）
• 若現有圖有 k 個連通分量，則至少需 k - 1 條新邊將它們串聯成樹
• 孤立點（度為 0）也是大小為 1 的連通分量

核心算法：並查集 — 近乎 O(1) 的動態連通性

並查集 是解決動態連通性問題的首選數據結構，支持：

• Find(x)：查找 x 所在集合代表元（路徑壓縮優化）
• Union(x, y)：合併兩集合（按秩/大小優化）

並查集完整實現（C++17）

#include 
using namespace std;

class DSU {
    vector parent, rank;
public:
    DSU(int n = 0) : parent(n+1), rank(n+1, 0) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]); // 路徑壓縮
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
    int countComponents(int n) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (find(i) == i) cnt++;
        return cnt;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    while (cin >> N >> M && N) {
        DSU dsu(N);
        for (int i = 0, a, b; i < M; ++i) {
            cin >> a >> b;
            dsu.unite(a, b); // 重複邊自動去重
        }
        int components = dsu.countComponents(N);
        cout << components - 1 << '\n';
    }
    return 0;
}

替代方案：DFS/BFS 深度/廣度優先搜索

適用於邊數較稠密或需輸出具體連通分量成員時：

// DFS 版本
vector> adj;
vector vis;

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    while (cin >> N >> M && N) {
        adj.assign(N+1, {});
        vis.assign(N+1, false);
        for (int i = 0, a, b; i < M; ++i) {
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        int comp = 0;
        for (int i = 1; i <= N; ++i)
            if (!vis[i]) { dfs(i); comp++; }
        cout << comp - 1 << '\n';
    }
}

複雜度對比

本題 N < 1000，兩種方法均輕鬆通過。**並查集代碼更短、常數更小、無遞歸風險，推薦首選。**

關鍵細節與避坑

1. 重複邊：並查集 `unite` 內部 `find` 相同則忽略，天然去重；DFS 需靠 `vis` 數組去重
2. 孤立點：初始 `parent[i]=i`，若無邊連接，`find(i)==i` 計為一分量，邏輯自動覆蓋
3. 輸入結束：N=0 終止，**該用例不處理**
4. 大數據 IO：題目提示 Huge input, scanf is recommended，C++ 用 ios::sync_with_stdio(false); cin.tie(nullptr); 同等效果
5. 樣例驗證：

   4 2        -> 城鎮 1,2,3,4；道路 1-3, 4-3 -> 分量: {1,3,4}, {2} -> 2-1=1 ✓
   3 3        -> 完全圖 -> 1 分量 -> 0 ✓
   5 2        -> 1-2, 3-5 -> 分量: {1,2}, {3,5}, {4} -> 3-1=2 ✓
   999 0      -> 999 孤立點 -> 999-1=998 ✓
   

舉一反三：相關經典題型

• 冗餘連接：LeetCode 684 — 找出導致環的那條邊（並查集檢測環）
• 省份數量：LeetCode 547 — 矩陣圖找連通分量（本題變體）
• 最小生成樹：Kruskal 算法核心即並查集 + 貪心
• 動態連通性：支持刪除邊的連通性查詢（需 LCT 或離線分治）

核心洞見： 「最少新建道路數 = 連通分量數 - 1」是圖論中**連通分量與生成樹關係**的直接推論。掌握並查集，即掌握了解決一大類動態連通性問題的通用鑰匙。