并查集

维护若干不相交集合,支持合并两个集合与查询元素所属集合。

标签 数据结构 / 并查集 / 等价类

定义

并查集(Union-Find / Disjoint Set Union)维护一个元素集合的划分:每个元素恰好属于一个不相交的子集。

它支持两种基本操作:

  • find(x):返回元素 𝑥 所属集合的代表元。
  • unite(x, y):把 𝑥 和 𝑦 所在的两个集合合并为一个。

通常用“森林”表示:每个集合是一棵树,树根就是代表元;find 沿父指针走到根,unite 把一棵树的根挂到另一棵树的根下。

不变量

  • 每个集合恰好有一棵树,树根是该集合的代表元。
  • 只有根节点的父指针指向自己,其余节点指向父节点。
  • find(x) 的结果只取决于 𝑥 当前所在的集合,与树的形状无关。

与图连通分量的关系

把图的每条边看成一次 unite,并查集就能维护无向图的连通分量:

  • 两个端点已经在同一集合,说明这条边连接的是同一个连通块。
  • 合并后,集合数量减少。

Kruskal 算法正是用这个性质判断“加入这条边会不会成环”。

常见误解

  • 认为 find(x) 返回 𝑥 的父亲:它返回的是集合的代表元(根)。
  • 认为路径压缩改变了集合划分:它只改变树的形状,不改变元素属于哪个集合。
  • 认为并查集支持删除:标准并查集只能合并,不能把集合拆开。
  • 认为 unite 一定要指定谁当根:谁当根不影响集合划分,只影响树的形状和后续效率。
源码位置