Yharim Area

Appearance

并查集

2021-06-01

简介 ​

并查集支持以下操作：

  • 往一个集合中加入元素；
  • 查询两个元素是否在同一集合；
  • 合并两个集合。

问题 ​

{a,b}，{e,c}，{e,d} 分别在同一个集合，则共有几个集合？b 和 d 是否同集？

构造 ​

把同集的两节点相连，则集合数 = 连通图数。若两节点连通，则它们同集。

并查集在每个集合中选取一个「代表元素」作为根节点，构造树型结构。

如图，a,e 分别为两集合的代表元素。

fa[i] 为节点 i 的父节点编号。上图中 fa[b]=a，fa[c]=e，fa[d]=e。

根节点的 fa 值都设为 0，即 fa[a]=0，fa[e]=0。

查询代表元素 ​

集合的「代表元素」就是并查集中的根节点。若节点 x 没有父节点，则它自己是根节点，否则递归查询它的父节点。

时间复杂度为 O(log⁡n)。

cpp
// 返回节点 x 的根节点祖先
int find(int x) {
    if (!fa[x])
        return x;
    return find(fa[x]);
}

查询是否同集 ​

若两个节点所在树的根节点相同，则它们同集。

cpp
bool judge(int x, int y) {
    return find(x) == find(y);
}

合并集合 ​

若 {b,c} 也同集，则合并其所在的集合。

将两集合根节点相连，即新建一条从 a 连向 e 的边，即设置 fa[e]=a。

cpp
void merge(int x, int y) {
    if (find(x) != find(y)) // 如果 x 和 y 已经同集，则不能再合并
        fa[find(x)] = find(y);
}

路径压缩 ​

  • 每次查询出节点 i 所在集合的根节点 e 后，使 fa[i]=e；
  • 再次查询 i 的根节点时，find(i) 函数就会直接返回 e，免去递归过程。

时间复杂度优化为 O(1)。该做法类似于 记忆化搜索。

cpp
int find(int x) {
    if (!fa[x])
        return x;
    return fa[x] = find(fa[x]); // 返回时保存
}