简介

并查集支持以下操作：

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

问题

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

构造

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

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

如图，$a,\phantom{0}$$\phantom{0}e$ 分别为两集合的代表元素。

a -> b
e -> c, d

$fa[i]$ 为节点 $i$ 的父节点编号。上图中 $fa[b]=\phantom{0}$$\phantom{0}a$，$fa[c]=\phantom{0}$$\phantom{0}e$，$fa[d]=\phantom{0}$$\phantom{0}e$。

根节点的 $fa$ 值都设为 $0$，即 $fa[a]=\phantom{0}$$\phantom{0}0$，$fa[e]=\phantom{0}$$\phantom{0}0$。

查询代表元素

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

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

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

查询是否同集

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

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

合并集合

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

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

a -> b
a -> e
e -> c, d

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

路径压缩

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

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

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