并查集
维护若干不相交集合,支持合并两个集合与查询元素所属集合。标签 数据结构 / 并查集 / 等价类
定义
并查集(Union-Find / Disjoint Set Union)维护一个元素集合的划分:每个元素恰好属于一个不相交的子集。
它支持两种基本操作:
find(x):返回元素 所属集合的代表元。unite(x, y):把 和 所在的两个集合合并为一个。
通常用“森林”表示:每个集合是一棵树,树根就是代表元;find 沿父指针走到根,unite 把一棵树的根挂到另一棵树的根下。
不变量
- 每个集合恰好有一棵树,树根是该集合的代表元。
- 只有根节点的父指针指向自己,其余节点指向父节点。
find(x)的结果只取决于 当前所在的集合,与树的形状无关。
与图连通分量的关系
把图的每条边看成一次 unite,并查集就能维护无向图的连通分量:
- 两个端点已经在同一集合,说明这条边连接的是同一个连通块。
- 合并后,集合数量减少。
Kruskal 算法正是用这个性质判断“加入这条边会不会成环”。
常见误解
- 认为
find(x)返回 的父亲:它返回的是集合的代表元(根)。 - 认为路径压缩改变了集合划分:它只改变树的形状,不改变元素属于哪个集合。
- 认为并查集支持删除:标准并查集只能合并,不能把集合拆开。
- 认为
unite一定要指定谁当根:谁当根不影响集合划分,只影响树的形状和后续效率。