Union-Find併查集

01為什麼需要它

看到這些關鍵字就想到它：在不在同一群、動態加邊、連通分量有幾個、加這條邊會不會成環、只合併不拆開。

02核心概念

併查集維護一堆互不相交的集合，只支援兩個操作：find(x) 回傳 x 所在集合的代表，union(a, b) 把兩個集合合併。它用一個 parent 陣列表示一片森林：每個集合是一棵樹，根就是代表，parent[根] = 根。find 就是沿著 parent 往上走到根；union 就是把一棵樹的根接到另一棵樹的根底下。

樸素版的樹可能長成一條鏈，find 變成 O(n)。兩個優化把它壓到幾乎常數。路徑壓縮：find 的回程把沿路每個節點的 parent 直接改成根，下次再問就是一步。按大小（或按秩）合併：永遠把小樹掛到大樹底下，樹高最多 log n。兩者一起用，m 次操作總共 O(m · α(n))，α 是反阿克曼函數，在任何實際的 n 下都不超過 5，所以當成常數。

它的限制也要記得：只能合併，不能拆開。需要刪邊的問題（例如「拿掉這條線之後還連通嗎」）通常反過來做：先把所有邊都不加，從最後一步倒著加回來。另外它只回答「連通與否」，不回答「怎麼走」，路徑要靠 BFS 或 DFS。

一個常被忽略的功能：union 回傳 false 表示兩端早就同群，也就是這條邊形成了環。無向圖偵測環、Kruskal 挑邊、判斷一組邊是不是樹，都靠這個訊號。

03演算法步驟

1. 1初始化 parent[i] = i、size[i] = 1、群數 count = n。
2. 2find(x)：parent[x] ≠ x 就遞迴找 parent[x] 的根，並把 parent[x] 改成那個根（路徑壓縮）。
3. 3union(a, b)：找兩邊的根。相同就回傳 false；不同就把 size 小的根接到大的底下，更新 size，count −= 1。
4. 4connected(a, b) 就是 find(a) == find(b)；連通分量數就是 count。
5. 5節點不是整數時，先用雜湊表把它們對應到 0..n−1。需要「刪邊」時考慮離線倒著做。

04互動示範

八個節點，依序執行一串 union 與 find。看 parent 陣列怎麼變、樹怎麼長，以及路徑壓縮發生時哪些節點被直接接到根。

05程式碼

含路徑壓縮與按大小合併的完整實作，附上連通分量計數與無向圖偵測環兩個最常見的用法。C++ 版用迭代的路徑減半，避免遞迴。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # 一開始每個人自己是根
        self.size = [1] * n              # 每棵樹的大小，合併時用
        self.count = n                   # 目前有幾群

    def find(self, x):
        """找根。路徑壓縮：回程時把沿路節點全部直接接到根"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        """合併兩群。回傳 False 表示本來就同群（這個訊號能偵測環）"""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:    # 按大小合併：小樹掛到大樹下
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


# 用法：算連通分量數（LeetCode 547 Number of Provinces 的核心）
uf = UnionFind(8)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7)]:
    uf.union(a, b)
print(uf.count)                 # 2 群：{0,1,2,3} 與 {4,5,6,7}
print(uf.connected(0, 4))       # False

# 無向圖偵測環：加一條邊時兩端已經同群，這條邊就成了環
def has_cycle(n, edges):
    uf = UnionFind(n)
    return any(not uf.union(a, b) for a, b in edges)

06練習題

• LeetCode 547Number of ProvincesMedium
• LeetCode 684Redundant Connection（偵測環）Medium
• LeetCode 200Number of Islands（用併查集再做一次）Medium
• LeetCode 721Accounts Merge（節點是字串）Medium
• LeetCode 1584Min Cost to Connect All Points（Kruskal 前置）Medium
• LeetCode 1319Number of Operations to Make Network ConnectedMedium