并查集
一个很强的数据结构，很多高级题目都有应用
作用
- 处理与连通性有关的问题
- 合并关联元素 查询元素见关联
- 查找公共父节点
操作
初始化
size为图中节点数pa记录各节点父节点
class Dsu:
def __init__(self, size):
self.pa = list(range(size)) # 记录父节点的数组查询
- 递归查找根节点
- 判定两个元素根节点是否相同
def find(self, x):
return x if self.pa[x] == x else self.find(self.pa[x])合并
- A B, 其中一个根节点的父节点指向另一个
def union(self, x, y):
self.pa[self.find(x)] = self.find(y)优化
路径压缩
- 递归过程将路径上元素的父节点修改为根节点
def find(self, x):
if self.pa[x] != x:
self.pa[x] = self.find(self.pa[x])
return self.pa[x]