并查集是非常灵活和高效的数据结构，常见应用是维护无向图的连通分量个数、大小，最小生成树的 Kruskal 算法和最近公共祖先等。
并查集维护了若干个不相交的集合，每个集合通过一棵树来组织，根节点为该集合的代表。
三个基本操作：
init(n)：初始化含有 \(n\) 个集合的并查集，每个集合的代表为自身。find(x)：寻找元素 \(x\) 所在集合的代表。union(x, y)：将元素 \(x,y\) 所在的集合合并，如果已经是处于同一集合的话就不合并。
一个简单的并查集示例，可以先看图理解，再理解代码结构。
并查集初始化、合并即查找图例
图示的一个关键理解是：当 fa[x] == x 时，说明 x 是根节点。
def __init__(self, n):self.fa = list(range(n + 1))
find 函数查找到元素所在集合的根，并且在查找过程中进行路径压缩（Path Compression）。
路径压缩目的是把树的高度压低，使得长链可以变成扁平的放射状，从而大大降低时间复杂度。
递归写法（直观、适合带权并查集写法）
def find(self, x):if self.fa[x] == x:return xroot = self.find(self.fa[x]) self.fa[x] = root return root
非递归写法（Python 推荐，避免栈溢出）
这里采用路径减半策略，效率高且代码简洁。
def find(self, x):while self.fa[x] != x:self.fa[x] = self.fa[self.fa[x]]x = self.fa[x]return x
在查找时当自身不是根时往上跳，跳到根节点，然后再返回的过程中改变途径节点的父节点，统一改成根。
合并的话先使用 find 函数找到对应的根，再链接即可。
def union(self, x, y):rx = self.find(x)ry = self.find(y)if rx != ry:self.fa[rx] = ry # 将 rx -> ry
这里也可以使用一个简单的启发式策略——按秩合并。维护一个 size 数组把小集合挂到大集合里去。
def union(self, x, y):rx = self.find(x)ry = self.find(y)if rx != ry:self.fa[rx] = ry # 将 rx -> ryif size[rx] > size[ry]:rx, ry = ry, rxself.fa[rx] = rysize[ry] += size[rx]
具体模板为
class DSU:def __init__(self, n):self.fa = list(range(n + 1))def find(self, x):while self.fa[x] != x:self.fa[x] = self.fa[self.fa[x]]x = self.fa[x]return xdef union(self, x, y):rx = self.find(x)ry = self.find(y)if rx != ry:self.fa[rx] = rydef is_same(self, x, y):rx = self.find(x)ry = self.find(y)return rx == ry