並查集：數位世界的官僚

演算法背後的故事：派對策劃人的難題

想像妳正在舉辦一場有 1000 位客人的大型派對。妳想知道兩個隨機的人，Alice 和 Bob，是否屬於同一個社交圈。

• Alice 認識 Carol。
• Carol 認識 Dave。
• Dave 認識 Bob。

如果每次都要順著這條鏈條去查，效率會非常低 ($O(N)$)。

1964 年，Bernard Galler 和 Michael Fisher 提出了一種類似於 政黨組織 的解決方案：每個人都屬於一個小組，每個小組都有一個 「代表」 (The Boss)。

如果妳問 Alice：「誰是妳的老大？」，她說「Carol」。問 Carol，她說「Dave」。問 Dave，他說「是我自己」。 如果妳問 Bob：「誰是妳的老大？」，他最終也指向「Dave」。 既然她們的老大是同一個人，她們就在同一個圈子裡。非常簡單。

但她們加入了一個叫做 路徑壓縮 (Path Compression) 的天才設計：下一次妳再問 Alice 時，她會跳過中間人，直接指著 Dave 說：「他是老大。」 這個簡單的技巧將層級結構徹底扁平化，使得查詢幾乎是瞬間完成的。

為什麼需要它？

並查集只為一件事而生：動態連通性 (Dynamic Connectivity)。

• 社群網路： 「妳和 X 有 5 個共同好友」背後的連通圖。
• 影像處理： Photoshop 的「魔棒」工具使用它來選中所有顏色相同的相連像素。
• Kruskal 演算法： 在構建最小生成樹（用最省錢的電纜連接城市）時，需要不斷檢查「這兩個城市是否已經連通了？」

演算法是如何「思考」的

這個演算法就像一個只有兩項工作的官僚：

1. Find (詢問)： 它問一個節點：「妳的領導是誰？」 如果這個節點指向別人，它就順藤摸瓜往上找，直到找到那個指向自己的「大老闆」。 關鍵最佳化： 在它回來的路上，它會悄悄告訴鏈路上的每個人：「順便說一句，大老闆是 Dave。下次別再層層匯報了，直接找他。」 (路徑壓縮)

2. Union (合併)： 它將兩個圈子合併。它找到 A 圈子的老大，對他說：「從現在起，妳向 B 圈子的老大匯報。」 最佳化： 它總是讓小圈子向大圈子匯報，以保持樹的層級盡可能淺。(按秩合併)

「反阿克曼函式」的奇蹟

並查集以其速度聞名。它的時間複雜度是 $O(\alpha(N))$，其中 $\alpha$ 是反阿克曼函式。 這是什麼概念？ 即使 $N$ 是宇宙中原子的總數，$\alpha(N)$ 也不會超過 4。 在工程實踐中，它實際上就是 常數時間 $O(1)$。

實作參考 (Python)

class UnionFind:
    def __init__(self, size):
        # 初始化：每個人的老大都是自己
        self.parent = list(range(size))
        # Rank 用於最佳化合併策略（誰聽誰的）
        self.rank = [1] * size

    def find(self, p):
        # 1. 路徑壓縮：官僚主義的捷徑
        if self.parent[p] != p:
            # 遞迴找到大老闆，並將我的直接上級改為大老闆
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]

    def union(self, p, q):
        # 2. 按秩合併：小弟聽大哥的
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP != rootQ:
            # 將較矮的樹掛在較高的樹下面
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1
            return True # 合併成功
        return False # 已經是自己人了

# 使用範例
# uf = UnionFind(10)
# uf.union(1, 2)
# uf.union(2, 5)
# print(uf.find(1) == uf.find(5)) # True

小結

並查集教會我們，管理複雜組織最好的方法就是 扁平化層級。透過賦予每個成員直接知曉「大老闆」的能力，它將一團亂麻的關係網變成了一個光速查詢系統。