Union-Find：判斷誰跟誰同國｜由淺至深演算法

想像你在玩朋友的朋友

一群人，有些人互為朋友。朋友的朋友也是朋友（傳遞關係）。有人問你：「A 和 Z 是不是同一群？」怎麼快回答？

笨方法：每次都從 A 開始走訪全部朋友看會不會走到 Z（BFS / DFS），每查一次 O(V+E)。

聰明方法：Union-Find（並查集）——每群選一個「老大」當代表，問同群只要看「兩人的老大是不是同一個」。

概念：每群一個代表

每個節點記住「我的老大是誰」（用 parent[x] 陣列），自己當老大時 parent[x] = x。

兩個操作

`find(x)`：找 x 的老大是誰

一路順著 parent 往上爬，直到爬到自己當老大的人。

find(D) → parent[D]=B → parent[B]=A → parent[A]=A（自己）→ 老大是 A

`union(x, y)`：把 x 和 y 合成一群

先各自 find 老大，把其中一個老大的 parent 指向另一個。

union(C, F):
  老大 X = find(C) = A
  老大 Y = find(F) = E
  parent[A] = E   (A 從此認 E 當老大)

→ 兩群合併

跑一遍

初始：5 個獨立的人 {0}{1}{2}{3}{4}，parent = [0,1,2,3,4]。

操作	parent 變化	結果
`union(0, 1)`	parent[0] = 1	`{0,1}{2}{3}{4}`
`union(2, 3)`	parent[2] = 3	`{0,1}{2,3}{4}`
`find(0)`	0 → 1 → 1（停）	老大是 1
`union(1, 3)`	find(1)=1, find(3)=3, parent[1]=3	`{0,1,2,3}{4}`
`find(0)`	0 → 1 → 3 → 3	老大是 3
`union(4, 0)`	find(4)=4, find(0)=3, parent[4]=3	`{0,1,2,3,4}` 全部一群

Pseudocode（基本版）

Algorithm find(x):

while parent[x] ≠ x:

x ← parent[x]

return x

Algorithm union(x, y):

rootX ← find(x)

rootY ← find(y)

if rootX ≠ rootY:

parent[rootX] ← rootY

基本版時間：最壞 O(n)（樹歪成鏈）。要加優化。

兩個必加優化

1. Union by Rank（按秩合併）

合併時讓較矮的樹掛到較高的樹底下，避免樹長高。

union(x, y):
  rootX = find(x), rootY = find(y)
  if rank[rootX] < rank[rootY]:
    parent[rootX] = rootY
  elif rank[rootX] > rank[rootY]:
    parent[rootY] = rootX
  else:
    parent[rootY] = rootX
    rank[rootX] += 1

2. Path Compression（路徑壓縮）

find(x) 時，順手把 x 一路到老大的所有節點都直接指向老大。下次再 find 直接 O(1)。

find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])  # 遞迴 + 改寫 parent
  return parent[x]

複雜度

加上兩個優化後，每次操作幾乎 O(1)——準確地說是 O(α(n))，α 是反 Ackermann 函數，n < 10²⁰ 時 α(n) < 5。

操作	基本版	+ 兩個優化
find	O(n)	O(α(n)) ≈ O(1)
union	O(n)	O(α(n)) ≈ O(1)

經典應用

Kruskal MST（下一章）：避免加入會形成環的邊。
連通分量：圖中有幾群互相連通的點。
動態連通性：邊一個個加入，問兩點是否連通。
離線查詢：把問題反過來處理（合併變拆分）。

📝考試會這樣考

題型一：跑一遍 union/find。 給操作序列，列出每步後的 parent 陣列。

題型二：講解 Path Compression。 畫圖：壓縮前是長鏈，壓縮後變扁平。

題型三：講解 Union by Rank 為什麼能保持樹高 O(log n)。 答：合併時矮的掛高的，總節點數翻倍才會讓高度+1，所以樹高 ≤ log n。

題型四：時間複雜度 α(n) 是什麼？ 答：反 Ackermann 函數。實務上 n ≤ 10²⁰ 都 < 5，可視為 O(1)。

這章記住

每群一個老大，parent[x] 記自己的爸爸，老大的爸爸是自己。
find 爬到老大、union 合併老大。
必加優化：Path Compression + Union by Rank → 幾乎 O(1)。
Kruskal MST 的好搭檔——下一節就用得到。