跳轉到

7.3 併查集Union-Find#

概念說明#

併查集（Union-Find / Disjoint Set） 管理「把 n 個元素劃分成若干互斥集合」，只支援兩個操作：

  • find(x)：x 屬於哪一組？（回傳該集合的「代表」）
  • union(x, y)：把 x、y 所在的兩組合併成一組。

它不支援隨意刪除、不記錄組內明細，但換來近乎 O(1) 的單次操作——這是資料結構史上「化約問題、極簡致勝」的最佳範例。經典應用：Kruskal 最小生成樹、判斷圖的連通性、社群好友圈合併、迷宮生成。

關鍵優化#

用「森林」表示：每個集合是一棵樹，parent[i] 指向父節點，根節點就是代表。兩個優化缺一不可：

  1. 路徑壓縮（path compression）：find 時順手把沿途節點全部直接掛到根上，樹越壓越扁。
  2. 按秩/大小合併（union by rank/size）：合併時把矮樹掛到高樹下，避免樹越長越高。

單獨任一優化是 O(log n)；兩者並用，n 次操作的總成本為 O(n·α(n))，α 是反阿克曼函數——在現實宇宙中 α(n) ≤ 4，可視為常數。

Python 實作#

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # 起初各自成組
        self.rank = [0] * n
        self.count = n                 # 組數

    def find(self, x):
        root = x
        while self.parent[root] != root:      # 先找到根
            root = self.parent[root]
        while self.parent[x] != root:         # 路徑壓縮：沿途全掛到根
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                       # 已同組（可用於偵測環）
        if self.rank[rx] < self.rank[ry]:      # 按秩合併：矮掛高
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

    def same_set(self, x, y):
        return self.find(x) == self.find(y)

# 好友圈問題：0..7 八個人
uf = UnionFind(8)
pairs = [(0, 1), (1, 2), (3, 4), (5, 6), (2, 7), (0, 7)]
for a, b in pairs:
    uf.union(a, b)
print("0 和 7 同圈？", uf.same_set(0, 7))    # True
print("3 和 5 同圈？", uf.same_set(3, 5))    # False
print("好友圈數：", uf.count)                 # 3 → {0,1,2,7} {3,4} {5,6}

# 環偵測：一條條加邊，若邊的兩端已在同組即出現環
g = UnionFind(4)
edges = [(0, 1), (1, 2), (2, 3), (0, 3)]
for u, v in edges:
    if not g.union(u, v):
        print(f"加入邊 ({u},{v}) 形成環！")     # (0,3) 形成環

操作步驟#

  1. 初始化：每個元素自成一棵單節點樹，parent[i] = i。
  2. find(x)：沿 parent 上溯到根；回程做路徑壓縮。
  3. union(x, y)：找兩個根；同根則已是同組；否則比較秩，把秩小的根掛到秩大的根下，必要時秩加一。

複雜度分析#

實現 find union
純樸（無優化） O(n) 最壞 O(n)
僅路徑壓縮 攤攤 O(log n) 攤攤 O(log n)
壓縮 + 按秩合併 攤攤 O(α(n)) ≈ O(1) 攤攤 O(α(n))

空間 O(n)。併查集的教訓值得銘記：若你只需要「等價類」資訊，就別用需要更多資訊的結構——簡化的表示法往往帶來更快的操作。

練習#

  1. 把「按秩合併」改成「按大小合併」（維護集合大小，小掛大），並加上 size(x) 回傳 x 所在集合的人數。
  2. 統計實驗：對 n=10⁶ 做 10⁶ 次隨機 union，比較「無優化」「僅路徑壓縮」「兩者並用」三版的總耗時。
  3. n 個人中有若干好友關係，好友圈內可互相傳遞訊息。給定關係串列與查詢「a 能否傳訊給 b」，用併查集離線處理，說明為何比每次 BFS 快。