跳至主要内容

Union Find (Disjoint Set)

Union Find（也稱作 Disjoint Set，中文常譯為「互斥集合」或「並查集」）是一種專門用來管理 「一群元素被分成好幾堆，互不相交的集合」 的資料結構。

白話理解

想像一場派對，一開始每個人都自己一夥。每當發現兩個人是朋友，就把他們的圈子合併起來。

Union Find 要解決的核心問題就是：「任意問兩個人，能不能快速知道他們是不是同一個朋友圈的？」

它主要提供兩個操作：

  • Find：查詢某個元素屬於「哪一個集合」（通常是回傳該集合的代表元素，稱為 Root 或 Representative）。
  • Union：把兩個集合合併成一個。

核心結構：用陣列記錄「誰是我的老大」​

Union Find 的底層通常只需要一個陣列 parent，parent[i] 記錄「元素 i 的上一層是誰」。如果 parent[i] === i，代表 i 自己就是這個集合的 Root（老大）。

一開始，每個元素都自己獨立成一個集合，所以 parent[i] = i。

初始狀態（5 個元素，各自獨立）：

index:    0  1  2  3  4
parent:   0  1  2  3  4

實作​

一個「陽春版」的 Find 和 Union 其實很簡單：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # 一開始每個人都是自己的老大

    def find(self, x):
        # 如果 x 不是自己的老大，就繼續往上找，直到找到 Root 為止
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return  # 本來就在同一國，不用合併

        self.parent[root_x] = root_y  # 讓其中一個 Root 認另一個 Root 當老大

這個陽春版本有個問題：如果一直把新元素接在同一條鏈的尾巴，鏈會越拉越長，find 就會退化成 O(n)。因此實務上一定會搭配兩個優化技巧：

優化一：Path Compression（路徑壓縮）​

在 find 的過程中，順便把沿路經過的每個節點，都直接接到 Root 底下，讓下一次查詢瞬間到位。

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # 遞迴往上找，順便把沿路的節點都接到 Root
    return self.parent[x]

優化二：Union by Rank / Size（依大小合併）​

合併時，永遠讓「規模較小的樹」接到「規模較大的樹」底下，避免樹越長越高。

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size  # 記錄每個 Root 底下大概的樹高（或元素數量）

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path Compression
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # 已經是同一國，合併失敗（可用來偵測環）

        # Union by Rank：矮的樹接到高的樹下面
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

逐步拆解：以 6 個元素為例​

依序執行 union(0, 1)、union(1, 2)、union(3, 4)、最後查詢 find(2) 是否等於 find(0)：

操作parent 陣列變化說明
初始化[0, 1, 2, 3, 4, 5]6 個元素各自獨立
union(0, 1)[0, 0, 2, 3, 4, 5]兩者 rank 相同，1 的 Root 接到 0 底下，0 的 rank 變成 2
union(1, 2)[0, 0, 0, 3, 4, 5]find(1) 沿路壓縮後是 0（rank 2），find(2) 是 2（rank 1），rank 較小的 2 接到 0 底下
union(3, 4)[0, 0, 0, 3, 3, 5]3、4 合併，邏輯同上，4 接到 3 底下
find(0)-0 本身就是 Root，直接回傳 0
find(2)-2 → 0（經過 Path Compression 直接指向 Root），Root 也是 0

因為 find(0) 和 find(2) 都是 0，可以立刻判斷 0 和 2 在同一個集合裡，完全不需要真的去走訪整個 Graph 找路徑。

複雜度​

同時使用 Path Compression 與 Union by Rank 優化後：

操作時間複雜度說明
Find近似 O(1)（嚴謹來說是 O(α(n))）α 是反阿克曼函數（Inverse Ackermann Function），成長極慢，在正常資料量下幾乎可以當作常數
Union近似 O(1)（同上）Union 內部呼叫了兩次 Find
資訊

不需要死記「反阿克曼函數」這個名詞，只要記得：同時做了 Path Compression 和 Union by Rank 之後，Union Find 的操作幾乎快到可以當成 O(1)，這是它最大的賣點。

適用情況​

  • 判斷兩個節點是否連通：例如社群網路中判斷兩人是否在同一個朋友圈、網路中判斷兩台機器是否能互相連線。
  • 判斷無向圖中是否有環（Cycle Detection）：依序處理每一條邊，如果要合併的兩個節點「早就已經是同一國」（union 回傳 false），代表這條邊會形成環。
  • 計算連通分量數量：例如 Leetcode: Number of Islands、社群網路中「總共有幾個互不相連的朋友圈」，也可以用 Graph Traversal 的 BFS/DFS 解決，但資料會動態一直新增連線時，Union Find 通常更方便。
  • 最小生成樹（Minimum Spanning Tree）：Kruskal's Algorithm 會依序嘗試加入權重最小的邊，並用 Union Find 判斷加入這條邊會不會形成環。

常見誤區​

  • 忘記做 Path Compression：沒有壓縮路徑的陽春版本，在最壞情況下 find 會退化成 O(n)，一定要記得在 find 的過程中把沿路節點都接到 Root。
  • 只用來判斷「有向圖」的環：Union Find 適合處理無向圖的連通性與環偵測。有向圖的環偵測，通常需要搭配 DFS（判斷是否走回目前遞迴路徑上的節點），或參考 Topological Sort 排序結果是否完整。
  • 誤以為 Union Find 能告訴你「路徑長什麼樣子」：Union Find 只能回答「兩個元素是否連通」，沒辦法像 Graph Traversal 或 Dijkstra's Algorithm 一樣還原出實際走過的路徑。
最後於 更新