[algorithms] Union-Find 並查集

視覺化概覽

graph TD
    subgraph 路徑壓縮前["Find 前"]
        A1["1 (根)"] --> B1["2"]
        B1 --> C1["3"]
        C1 --> D1["4"]
    end

    路徑壓縮前 -- "find(4) 路徑壓縮" --> 路徑壓縮後

    subgraph 路徑壓縮後["Find 後"]
        A2["1 (根)"] --> B2["2"]
        A2 --> C2["3"]
        A2 --> D2["4"]
    end

    style 路徑壓縮前 fill:#fff3e0,stroke:#ff9800
    style 路徑壓縮後 fill:#e8f5e9,stroke:#4caf50

什麼是 Union-Find？

管理「誰和誰是一夥的」的資料結構。

又稱 Disjoint Set Union (DSU)。

初始：每個人自成一組
{0} {1} {2} {3} {4}

union(1, 2)：1 和 2 合併
{0} {1,2} {3} {4}

union(3, 4)：3 和 4 合併
{0} {1,2} {3,4}

union(2, 3)：2 和 3 合併 → 整組合併
{0} {1,2,3,4}

核心操作

1. Find - 找根節點

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

2. Union - 合併集合

void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

3. Connected - 是否同組

boolean connected(int x, int y) {
    return find(x) == find(y);
}

優化技巧

1. 路徑壓縮

把路徑上所有節點直接指向根：

壓縮前:          壓縮後:
    1               1
    |             / | \
    2            2  3  4
    |
    3
    |
    4

2. 按秩合併

矮的樹接到高的樹下面：

if (rank[rootX] < rank[rootY]) {
    parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
    parent[rootY] = rootX;
} else {
    parent[rootY] = rootX;
    rank[rootX]++;
}

時間複雜度

操作	無優化	有優化
find	O(n)	O(α(n)) ≈ O(1)
union	O(n)	O(α(n)) ≈ O(1)

α(n) 是反阿克曼函數，對於任何實際 n，α(n) ≤ 4

經典應用

1. 判斷圖的連通性

// 給定邊列表，判斷有幾個連通分量
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
    uf.union(edge[0], edge[1]);
}
return uf.getCount();

2. 檢測環

// 無向圖中，如果合併時兩點已連通，則有環
for (int[] edge : edges) {
    if (uf.connected(edge[0], edge[1])) {
        return true; // 有環
    }
    uf.union(edge[0], edge[1]);
}
return false;

3. Kruskal 最小生成樹

// 按邊權重排序，依序加入不形成環的邊
Arrays.sort(edges, (a, b) -> a.weight - b.weight);
for (Edge e : edges) {
    if (!uf.connected(e.u, e.v)) {
        uf.union(e.u, e.v);
        mst.add(e);
    }
}

4. 動態連通性

判斷兩點在動態加邊過程中何時首次連通。

變體

帶權重的並查集

用於計算比值關係：

已知：a/b = 2, b/c = 3
求：a/c = ?

答案：6

void union(int x, int y, double w) {
    // x / y = w
    parent[rootX] = rootY;
    weight[rootX] = weight[y] * w / weight[x];
}
 
double query(int x, int y) {
    return weight[x] / weight[y];
}

常見題目

1. 冗餘連接 - LeetCode 684
2. 島嶼數量 - LeetCode 200（可用 UF 解）
3. 朋友圈 - LeetCode 547
4. 等式方程可滿足性 - LeetCode 990
5. 除法求值 - LeetCode 399（帶權重）

實作模板

class UnionFind {
    int[] parent, rank;
    int count;
 
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
 
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
 
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        count--;
        return true;
    }
 
    boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

相關檔案

• Java 實作：UnionFind.java