在數據結構的世界裏，有一種叫做並查集（Union-Find）的工具，它專門用來解決一類“集合合併”和“元素歸屬”的問題。比如，我們可能想知道“小明和小紅是不是在同一個朋友圈”，或者“兩個網絡節點是否連通”，這些問題都可以用並查集來高效解決。
並查集的基本操作¶
並查集主要有兩個核心操作：find（查找元素所在集合的根節點）和union（合併兩個集合）。爲了理解這兩個操作，我們先假設有一個簡單的場景：
我們有編號爲1到5的5個元素，一開始每個元素都是自己的“集合”，就像每個人都屬於自己的朋友圈。我們用一個數組parent來記錄每個元素的“父節點”（即直接指向的上一級元素），初始時parent[i] = i（自己是自己的父節點）。
1. find操作：找“祖宗”¶
find(x)的目標是找到元素x所在集合的“根節點”（即這個集合的“祖宗”）。比如，如果我們合併了1和2，那麼parent[2] = 1，此時find(2)的結果就是1（因爲2的父節點是1，而1的父節點是自己，所以1是根）。
基礎版find的邏輯很簡單：
def find(x):
while parent[x] != x: # 如果x的父節點不是自己，就一直向上找
x = parent[x]
return x # 找到根節點，返回
2. union操作：合併集合¶
union(x, y)的目標是把x和y所在的兩個集合合併成一個。比如，我們要合併1和2所在的集合，只需要讓其中一個集合的根指向另一個集合的根。
基礎版union的邏輯是：
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x != root_y:
parent[root_y] = root_x # 讓y的根指向x的根
基礎版並查集的問題：查找太慢了！¶
基礎版並查集雖然能用，但在某些場景下效率很低。比如，當我們多次合併後，集合可能形成一個“長鏈”結構：
假設我們依次合併了1-2、2-3、3-4、4-5，此時parent數組的狀態會是：
parent[1]=1，parent[2]=1，parent[3]=2，parent[4]=3，parent[5]=4。
這時，如果我們要find(5)，需要依次經過5→4→3→2→1，才能找到根節點1。如果這樣的“長鏈”很長（比如合併了1000個元素），每次find都要走1000步，效率就會變得很低。
路徑壓縮：讓查找“一步到位”¶
爲了解決長鏈問題，路徑壓縮（Path Compression）應運而生。它的核心思想是：在每次find操作中，讓路徑上的每個節點直接指向根節點，這樣下次查找時路徑會被“扁平化”，幾乎“一步到位”。
路徑壓縮的原理¶
想象你在爬山，本來需要經過很多臺階才能到山頂（根節點）。路徑壓縮就像在你爬的過程中，每次遇到臺階就直接把你拉到山頂，下次再爬時，你直接從山頂出發，不需要再走臺階了。
具體實現時，我們可以在find函數中對路徑上的每個節點進行“壓縮”：當遞歸找到根節點後，把路徑上所有節點的父節點都直接設爲根。
帶路徑壓縮的find實現¶
以下是帶路徑壓縮的find函數（遞歸版）：
def find(x):
if parent[x] != x: # 如果x不是根節點
# 遞歸找到根節點，並把父節點直接設爲根
parent[x] = find(parent[x])
return parent[x]
舉個例子：
假設合併後形成的長鏈是5→4→3→2→1（即parent[5]=4，parent[4]=3，parent[3]=2，parent[2]=1，parent[1]=1）。
-
第一次
find(5)：
遞歸執行find(4)→find(3)→find(2)→find(1)（此時parent[1]=1，返回1）。
然後parent[2]被設爲1，parent[3]被設爲1，parent[4]被設爲1，parent[5]被設爲1。
此時parent數組變爲：parent[5]=1，parent[4]=1，parent[3]=1，parent[2]=1，parent[1]=1。 -
第二次
find(5)：
直接parent[5] = 1，返回1，路徑長度從5步變成1步！
迭代版路徑壓縮（更直觀）¶
如果覺得遞歸版難理解，也可以用迭代方式實現路徑壓縮：
def find(x):
# 第一步：找到根節點
root = x
while parent[root] != root:
root = parent[root]
# 第二步：把路徑上所有節點的父節點設爲根（路徑壓縮）
while parent[x] != root:
next_parent = parent[x] # 記錄當前父節點
parent[x] = root # 直接指向根
x = next_parent # 繼續處理下一個節點
return root
這個迭代版本先找到根節點，再從起點開始，把每個節點的父節點直接設爲根，確保路徑最短。
路徑壓縮的效果：幾乎O(1)的查找效率¶
路徑壓縮讓find操作的時間複雜度從基礎版的O(h)（h爲樹的高度）優化到接近O(1)。即使是對100萬個元素的集合，經過路徑壓縮後，查找一次的時間也幾乎可以忽略不計。
這是因爲每次路徑壓縮都會讓樹的結構變得更扁平，最終每個節點都會直接指向根，形成一棵“矮胖”的樹。
總結¶
路徑壓縮是並查集的“加速魔法”，它通過在查找過程中讓所有節點直接指向根節點，把原本可能很長的路徑壓縮成“一步到位”。結合並查集的其他優化（如按秩合併），它能在幾乎常數時間內完成合並和查找操作，成爲解決“集合問題”的核心技術。
下次遇到需要快速判斷元素歸屬的問題時，記得用並查集+路徑壓縮，讓你的代碼飛起來吧！