並查集（Union-Find）教學：原理、程式碼與時間複雜度

並查集解決什麼問題

想像一個電腦網路，纜線被一條一條加進來，而每加一條，你都得回答「電腦 A 和電腦 B 有連通嗎？」。每個問題都跑一次圖搜尋，每次要花 O(n + m)。並查集則在加入纜線的同時維護連通的群組，因此每個問題幾乎都能在 O(1) 內回答。

同樣的需求也出現在 Kruskal 最小生成樹演算法（這兩個端點是否已屬於同一棵樹？）、偵測無向圖中的環、把共用同一個電子郵件的帳號分組、滲流（percolation）模擬，以及影像處理中標記連通區域。

用白話理解

每個元素都指向一個父節點。指向自己的元素就是根，而根就是整個群組的代表。要找到 x 所屬的群組，就沿著父指標一路走到根。要合併兩個群組，就找出兩個根，讓其中一個根指向另一個。

兩項最佳化可以讓樹保持扁平：

• 按秩（或按大小）合併：把較矮（或較小）的樹接到較高（或較大）的樹底下，這樣只有在兩棵相等的樹合併時，樹的高度才會增加。
• 路徑壓縮：在 find 的過程中，讓路徑上的每個節點都直接指向根，下次查找就只需一步。

實例演練：五個元素

從元素 0 到 4 開始，每個元素各自成一組。父陣列是 [0, 1, 2, 3, 4]。我們使用按大小合併，大小相等時讓第二個根成為子節點。

Python 實作

這個版本使用按大小合併，以及帶路徑壓縮的迭代式 find，所以不會有遞迴深度的問題。當兩個元素原本就在同一組時，union 會回傳 False，這對偵測環很有用。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:       # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

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

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

範例：偵測無向圖中的環

逐一處理每條邊。如果一條邊的兩個端點已經有相同的根，這條邊就會形成環。Kruskal 演算法在依權重排序邊之後，用的正是這個檢查。

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))  # True

時間與空間複雜度

α(n) 是反 Ackermann 函數，成長得極其緩慢，對於真實電腦可能容納的任何 n，它最多只有 4。實務上這代表每次操作都是常數時間。Robert Tarjan 在 1975 年證明了這個界限。父陣列與大小陣列的空間為 O(n)。

變體與常見錯誤

• 比較元素而不是比較根：union 必須連接 find(a) 與 find(b)，而不是 a 和 b 本身。
• 以為 parent[x] 就是代表元素。經過多次 union 之後，只有 find(x) 才是正確的；在依父節點分組之前，要先對每個元素呼叫 find。
• 在沒有按秩合併的情況下，對大型輸入使用遞迴的 find 可能碰到 Python 的遞迴上限；上面的迭代版本可以避免這個問題。
• 元素不是 0 到 n-1 的整數：先用 dict 把它們對應到索引，或把父節點存在 dict 中，並以延遲方式新增元素。
• 並查集無法拆分群組。如果邊被刪除，就需要不同的資料結構，或是以反向處理刪除的離線方法。
• 帶權並查集會在每個節點上儲存到父節點的偏移量，可以回答像「a 比 b 重多少？」這樣的問題。

何時使用，以及常見問題

當群組只會合併，而你需要詢問兩個元素是否在同一組，或一共有多少個群組時，請使用並查集。對於靜態圖上的單一連通性問題，單純的 BFS 或 DFS 更簡單。如果需要實際的路徑，請改用圖搜尋，因為並查集只知道成員關係。

常見題目：連通元件的數量、島嶼數量（以網格儲存格為元素）、冗餘連接（形成環的那條邊）、帳號合併、像 a == b, b != c 這種等式方程式的可滿足性，以及 Kruskal 最小生成樹。