HDU 1232 暢通工程：並查集 (Union-Find) 計算需添加邊數

問題描述

給定 n 個城市，m 條已建道路。道路連接的城市之間可相互到達。求**最少還需建設多少條道路**，使任意兩城市連通。即：求圖的連通分量數 k，答案為 k - 1。多測試用例，n=0 結束。

算法選型：並查集 (Disjoint Set Union, DSU)

• 動態維護連通分量，合並操作 O(α(n)) 接近常數。
• 初始每城市自成一集 (tot = n-1 為理想最少邊數)。
• 每輸入一條邊 (x,y)，若 find(x) != find(y)，則 union(x,y) 並 tot--。
• 最終 tot 即為答案。

完整代碼 (C 路徑壓縮優化)

#include 
#include 

#define MAXN 1001

int parent[MAXN];
int tot; // 需添加的邊數 = 連通分量數 - 1

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]); // 路徑壓縮
    return parent[x];
}

void unite(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa != fb) {
        parent[fa] = fb;
        --tot; // 合並兩個分量，所需邊數 -1
    }
}

int main() {
    int n, m, x, y;
    while (scanf("%d", &n) == 1 && n) {
        scanf("%d", &m);
        tot = n - 1; // 初始 n 個孤立點，需 n-1 條邊連通
        for (int i = 1; i <= n; ++i) parent[i] = i; // 初始化

        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &x, &y);
            unite(x, y);
        }
        printf("%d\n", tot);
    }
    return 0;
}

核心邏輯圖解

初始: n=4, tot=3
城市: 1  2  3  4  (各自為集)

輸入邊 (1,2): find(1)!=find(2) -> unite -> tot=2  集合: {1,2} {3} {4}
輸入邊 (3,4): find(3)!=find(4) -> unite -> tot=1  集合: {1,2} {3,4}
輸入邊 (2,3): find(2)!=find(3) -> unite -> tot=0  集合: {1,2,3,4} 全連通
答案: 0

優化要點

1. 路徑壓縮：find 遞歸賦值，將沿路節點直接掛到根節點。
2. 按秩合並 (可選)：維護 rank[] 或 size[]，小樹掛大樹，進一步降低樹高。本題 n≤1000 單純壓縮已足夠。
3. 初始化 tot = n-1：直觀理解「連通 n 個孤立點最少需 n-1 條邊」，每次合並減 1。

複雜度

• 時間：O(m α(n)) ≈ 線性，極快。
• 空間：O(n)。

擴展：輸出具體添加方案

若需輸出具體添加哪些邊：遍歷所有城市對 (i,j)，若 find(i)!=find(j) 輸出並 unite，直到 tot==0。但本題僅需數量。