在数据结构的世界里，有一种叫做并查集（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万个元素的集合，经过路径压缩后，查找一次的时间也几乎可以忽略不计。
这是因为每次路径压缩都会让树的结构变得更扁平，最终每个节点都会直接指向根，形成一棵“矮胖”的树。
总结¶
路径压缩是并查集的“加速魔法”，它通过在查找过程中让所有节点直接指向根节点，把原本可能很长的路径压缩成“一步到位”。结合并查集的其他优化（如按秩合并），它能在几乎常数时间内完成合并和查找操作，成为解决“集合问题”的核心技术。
下次遇到需要快速判断元素归属的问题时，记得用并查集+路径压缩，让你的代码飞起来吧！