并查集

并查集支持以下操作：

• 往一个集合中加入元素；

• 查询两个元素是否在同一集合；

• 合并两个集合.

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

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

并查集在每个集合中选取一个代表元素作为根节点，构造树型结构. 如图，$a,e$ 分别为两集合的代表元素.

flowchart
a --> b
e --> c
e --> d

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

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

集合的代表元素就是并查集中的根节点.若节点 $x$ 没有父节点，则它自己是根节点，否则递归查询它的父节点.时间复杂度为 $O(\log{n})$.

int find(int x) { // 返回节点 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]=a$.

flowchart
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]=e$.

• 再次查询 $i$ 的根节点时，find(i) 函数就会直接返回 $e$，免去递归过程.

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

int find(int x) {
    if(!fa[x]) return x;
    return fa[x] = find(fa[x]);
    // 最后一行等价于 { fa[x] = find(fa[x]); return fa[x]; }
}