[algorithms] Union-Find 並查集

「這兩個人是不是同一個群組的？」——Union-Find 用接近 O(1) 的速度回答你。

先講結論

Union-Find 管理「分組」：合併兩組、查詢兩人是否同組。加上路徑壓縮和按秩合併，兩個操作都是 O(α(n))，α(n) 是反阿克曼函數——對任何實際的 n 都 ⇐ 4，等同常數。經典應用：圖的連通性、環檢測、Kruskal 最小生成樹。

核心概念

每個人一開始自成一組，用一個 parent 陣列追蹤「我的老大是誰」。同組的人最終都指向同一個根。

初始: {0} {1} {2} {3} {4}     每個人指向自己

union(1,2): {0} {1,2} {3} {4}   1 和 2 同一組了
union(3,4): {0} {1,2} {3,4}     3 和 4 同一組了
union(2,3): {0} {1,2,3,4}       整組合併

三個操作

// Find：找根節點（加路徑壓縮）
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]); // 順便把路徑壓扁
    return parent[x];
}
 
// Union：合併
void union(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) parent[px] = py;
}
 
// Connected：是否同組
boolean connected(int x, int y) {
    return find(x) == find(y);
}

就這樣。核心邏輯不到 15 行。

路徑壓縮：讓 find 越來越快

沒壓縮的話，tree 可能退化成鏈表，find 要走 O(n)。路徑壓縮在每次 find 時，把沿途所有節點直接指向根：

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

下次再 find(4)，一步就到根。整棵樹越用越扁。

按秩合併：矮的接到高的下面

if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else { parent[py] = px; rank[px]++; }

避免把高的樹接到矮的下面，控制樹高。路徑壓縮 + 按秩合併，兩個一起用效果最好。

經典應用

環檢測：在無向圖中，加邊時如果兩端點已經 connected，代表形成了環。

for (int[] edge : edges) {
    if (connected(edge[0], edge[1])) return true; // 有環！
    union(edge[0], edge[1]);
}

Kruskal 最小生成樹：邊按權重排序，每次取最小的邊，如果兩端不在同一組就加入。Union-Find 讓「是否同組」的檢查幾乎是 O(1)。

連通分量計數：把所有邊 union 完，數有幾個不同的根就知道有幾個連通分量。

帶權重的 Union-Find：可以追蹤節點之間的比值關係。LeetCode 399「除法求值」就是這個應用——已知 a/b=2, b/c=3，求 a/c。

完整模板

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;
    }
}

背下來，面試直接默寫。真的，Union-Find 的模板是 CP 值最高的背誦投資。

---

Union-Find 的設計哲學：我不在乎你們怎麼認識的，我只在乎你們最終是不是同一掛的。