D006 【模板】并查集

并查集维护了若干个不相交的集合每个集合通过一棵树来组织根节点为该集合的代表。三个基本操作init(n)初始化含有 n 个集合的并查集每个集合的代表为自身。find(x)寻找元素 x 所在集合的代表。union(x, y)将元素 ,x,y所在的集合合并如果已经是处于同一集合的话就不合并。一个简单的并查集示例可以先看图理解再理解代码结构。并查集初始化、合并及查找图例图示的一个关键理解是当fa[x] x时说明x是根节点。很多题目按这个来找所有集合的代表比如将所有连通分量相连时就可以按root1 - root2, root2 - root3 ···来将分量连起来初始化初始化代码def __init__(self, n): self.fa list(range(n 1))find函数find函数查找到元素所在集合的根并且在查找过程中进行路径压缩Path Compression。路径压缩目的是把树的高度压低使得长链可以变成扁平的放射状从而大大降低时间复杂度。递归写法直观、适合带权并查集写法def find(self, x): if self.fa[x] x: return x root 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 - ry if size[rx] size[ry]: rx, ry ry, rx self.fa[rx] ry size[ry] size[rx]获取根数组一个很重要的操作利用前面提到的理解当fa[x] x时说明x是根节点。获取所有集合的根。def get_root(self): return [x for x in range(1, len(self.fa)) if self.fa[x] x]模板具体模板为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 x def union(self, x, y): rx self.find(x) ry self.find(y) if rx ! ry: self.fa[rx] ry def is_same(self, x, y): # 判断两元素是否在同一集合 rx self.find(x) ry self.find(y) return rx ry def get_root(self): return [x for x in range(1, len(self.fa)) if self.fa[x] x]