想象一下，你是一個班級的班長，班裏有很多同學。現在有一些同學互相認識（是朋友），但你需要快速知道：哪些同學是通過朋友關係連在一起的？比如，A認識B，B認識C，那麼A、B、C應該是同一類人。同時，你還需要能快速判斷兩個同學是否認識（即使他們沒直接說過話，但有共同認識的人也行）。這時候，有什麼數據結構能幫你高效地解決這個問題呢？答案就是——並查集。
一、並查集是什麼？¶
並查集（Union-Find）是一種用於管理元素分組的高效數據結構，核心功能是解決兩個問題：
1. 合併（Union）：把兩個不同的“組”（集合）合併成一個組；
2. 查詢（Find）：判斷兩個元素是否屬於同一個組。
它的名字裏“並”對應“合併”，“查”對應“查詢”，非常直觀。
二、並查集的基本原理¶
並查集的底層用一個數組 parent 來表示每個元素的“父節點”。我們可以把每個組想象成一棵“樹”，根節點（父節點指向自己的節點）是這個組的“代表”。
- 初始時，每個元素都是自己的組，所以 parent[i] = i（假設元素用數字編號）。
- Find 操作：查找元素的根節點（即它所在的組的代表）。
- Union 操作：將兩個元素所在的組合並，讓其中一個組的根節點指向另一個組的根節點。
舉個例子：用並查集管理“朋友關係”¶
假設我們有 5 個人：小明（0）、小紅（1）、小剛（2）、小李（3）、小芳（4）。初始時，每個人都是自己的組（parent = [0,1,2,3,4]）。
步驟 1：小明和小紅是朋友
- 小明的根是 0，小紅的根是 1。
- 合併兩個組：讓小紅的父節點指向小明的根（parent[1] = 0）。現在小紅和小明在同一個組，根是 0。
步驟 2：小剛和小紅是朋友
- 小剛的根是 2，小紅的根是 0（因爲 parent[1]=0，小紅的父節點是 0）。
- 合併兩個組：讓小剛的父節點指向 0（parent[2] = 0）。現在小剛、小明、小紅在同一個組，根是 0。
步驟 3：小李和小明是朋友
- 小李的根是 3，小明的根是 0。
- 合併兩個組：讓小李的父節點指向 0（parent[3] = 0）。現在小李、小明、小紅、小剛在同一個組，根是 0。
查詢：判斷小芳（4）是否和小明是朋友？
- 小芳的根是 4，小明的根是 0，根不同，所以不是朋友。
三、優化：讓並查集更快¶
上面的例子是“樸素”的並查集，但如果合併和查詢操作太多，樸素實現可能會變慢（比如樹退化成鏈表）。路徑壓縮和按秩合併是關鍵優化：
1. 路徑壓縮：讓“彎路”變“直路”¶
每次 Find 操作後，把路徑上所有節點的父節點直接指向根節點。
比如，原來的路徑是 A → B → C → 根，壓縮後變成 A → 根、B → 根、C → 根，下次查詢時直接一步到位。
比喻：就像你去學校需要繞很多彎路，老師讓你下次直接抄近路，以後就不用再繞了。
2. 按秩合併：讓“小樹”依附“大樹”¶
合併兩個組時，把“樹的高度較小”的組合併到“樹的高度較大”的組的根節點下。
比喻：合併兩個小組時，讓矮個子小組（小樹）的根指向高個子小組（大樹）的根，避免大樹被“壓彎”。
四、並查集的核心代碼（簡化版）¶
以下是用 Python 實現的並查集（含路徑壓縮和按秩合併）：
class UnionFind:
def __init__(self, size):
self.parent = list(range(size)) # 父節點數組，初始每個元素自己是根
self.rank = [0] * size # 秩數組，記錄樹的高度
def find(self, x):
# 路徑壓縮：找到根節點，並把路徑上的節點直接指向根
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 遞歸壓縮父節點
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
# 矮樹合併到高樹
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1 # 合併後高樹高度+1
五、應用場景¶
並查集看似簡單，卻能解決很多實際問題：
- 網絡連接：判斷兩臺電腦是否在同一個局域網（通過路由器連接）。
- 家族關係：判斷兩個人是否有血緣關係（族譜合併）。
- 最小生成樹：在 Kruskal 算法中，用並查集判斷加入一條邊後是否會形成環。
- 數學問題：比如判斷兩個數是否屬於同一個等價類（如模運算下的等價關係）。
六、總結¶
並查集的核心是用數組維護“父節點”關係，通過 find 和 union 操作高效管理集合。路徑壓縮和按秩合併是關鍵優化，讓它能在接近常數的時間複雜度下處理大量操作。它就像一個“高效的小組管理員”，無論合併還是查詢，都能快速給出結果。
如果你遇到“分組”問題（比如判斷是否在同一個集合），並查集會是一個簡單又強大的工具！