D006 【模板】并查集

并查集是非常灵活和高效的数据结构，常见应用是维护无向图的连通分量个数、大小，最小生成树的 Kruskal 算法和最近公共祖先等。
并查集维护了若干个不相交的集合，每个集合通过一棵树来组织，根节点为该集合的代表。
三个基本操作：

• init(n) ：初始化含有 \(n\) 个集合的并查集，每个集合的代表为自身。
  
• find(x) ：寻找元素 \(x\) 所在集合的代表。
  
• union(x, y) ：将元素 \(x,y\) 所在的集合合并，如果已经是处于同一集合的话就不合并。
  

一个简单的并查集示例，可以先看图理解，再理解代码结构。
   

    并查集初始化、合并即查找图例图示的一个关键理解是：当 fa[x] == x 时，说明 x 是根节点。很多题目按这个来找所有集合的代表，比如将所有连通分量相连时，就可以按 root1 - root2, root2 - root3 ··· 来将分量连起来
初始化代码为

1. def __init__(self, n):
2.     self.fa = list(range(n + 1))

复制代码

find 函数查找到元素所在集合的根，并且在查找过程中进行路径压缩（Path Compression）。
路径压缩目的是把树的高度压低，使得长链可以变成扁平的放射状，从而大大降低时间复杂度。
递归写法（直观、适合带权并查集写法）

1. def find(self, x):
2.     if self.fa[x] == x:
3.         return x
4.    
5.     root = self.find(self.fa[x])
6.     self.fa[x] = root
7.     return root

复制代码

非递归写法（Python 推荐，避免栈溢出）
这里采用路径减半策略，效率高且代码简洁。

1. def find(self, x):
2.     while self.fa[x] != x:
3.         
4.         self.fa[x] = self.fa[self.fa[x]]
5.         x = self.fa[x]
6.     return x

复制代码

在查找时当自身不是根时往上跳，跳到根节点，然后再返回的过程中改变途径节点的父节点，统一改成根。
合并的话先使用 find 函数找到对应的根，再链接即可。

1. def union(self, x, y):
2.     rx = self.find(x)
3.     ry = self.find(y)
4.     if rx != ry:
5.         self.fa[rx] = ry  # 将 rx -> ry

复制代码

这里也可以使用一个简单的启发式策略——按秩合并。维护一个 size 数组把小集合挂到大集合里去。

1. def union(self, x, y):
2.     rx = self.find(x)
3.     ry = self.find(y)
4.     if rx != ry:
5.         self.fa[rx] = ry  # 将 rx -> ry        if size[rx] > size[ry]:            rx, ry = ry, rx        self.fa[rx] = ry        size[ry] += size[rx]

复制代码

具体模板为

1. class DSU:
2.     def __init__(self, n):
3.         self.fa = list(range(n + 1))
4.    
5.     def find(self, x):
6.         while self.fa[x] != x:
7.             self.fa[x] = self.fa[self.fa[x]]
8.             x = self.fa[x]
9.         return x
10.    
11.     def union(self, x, y):
12.         rx = self.find(x)
13.         ry = self.find(y)
14.         if rx != ry:
15.             self.fa[rx] = ry
16.    
17.     def is_same(self, x, y):
18.         rx = self.find(x)
19.         ry = self.find(y)
20.         return rx == ry

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！