并查集

并查集，Disjoint-Set，或者通俗一点，叫做MergeFind-Set，是一种可以动态维护若干个不重叠的集合，并支持集合之间的合并与查询的数据结构。

集体来说，并查集支持下列两个操作：

• Find，查询元素所属集合

• Merge，将两个元素所属集合合并

一般来说，为了具体实现，我们将每一个集合选择一个固定的元素，作为整个集合的代表

所以，假设我们的元素是一堆整数，则，可以有

// N需要根据实际情况调整，grp是group的缩写
int grp[N];

初始化则设每一元素所在的组是其本身

for (int i = 0; i <= n; ++i) grp[i] = i;

做完了准备工作，我们需要思考如何合并？

考虑我们可以使用树形结构来储存，则，每一个树根都应该满足grp[root] = root。

于是我们只需要修改树根就行了，即grp[root(x)] = root(y)

那么，问题来了，如何寻找根？

回到上述定义中的树形结构及其性质，则很容易可以推出一个递归算法：

int find(int x) {
    if (grp[x] != x) return find(grp[x]);
    return x;
}

于是，合并的算法也就可以写出来了

int merge(int x, int y) {
    grp[find(x)] = find(y);
}

优化

优化方案有3：路径压缩，启发式合并，按秩合并。

路径压缩

其实，我们把整个grp的关系链画出来

实际上，我们可以不关注树的形状，意味着上图中的树实际上等价于

这样，我们就可以在find中将这个元素直接连接到其父节点上

则有

int find(int x) {
    if (grp[x] != x) return grp[x] = find(grp[x]);
    return x;
}

其实很多时候，只用路径压缩就已经够了

启发式合并

看上去很高级的名字，其实原理很简单

我们新建一个cnt数组，由于记录每一个元素所在集合中有多少个元素，在合并时，将元素多的作为根，则可以相对优化。

但是，毕竟是启发式合并，元素多的并不一定层数少，这是一个概率问题……

但好处是，启发式合并可以和路径压缩一起使用，这比只使用路径压缩快了一些，并且代码复杂度比较简单。所以我就不提供参考代码了

按秩合并

这里的秩就是指树的深度，那么，为了优化，很明显，我们需要将层数少的合并到层数多的树中，且层数少的合并到层数多的并不会影响层数多的层数。

但是，如果两者层数相等呢？

举个例子，我们要合并1和4。

那么由于两棵树层数相等，所以无论哪一个作为主树都可（假设我们以1为主树）

则合并之后应该时

可以发现，层数变多了……所以说，秩需要+1

分析完毕，代码该如何写？

首先时初始化，由于刚开始每一个元素都是一颗树，所以秩为1

int rank[N]; // 储存每一个元素的秩
for (int i = 0; i <= n; ++i) {
    rank[i] = 1;
    grp[i] = i;
}

寻找的代码不变

合并代码如下

void merge(int x, int y) {
    int gx = find(x), gy = find(y);
    if (rank[gx] <= rank[gy])
        grp[gx] = gy;
    else
        grp[gy] = gx;
    if (rank[gx] == rank[gy] && gx != gy) // 防止合并相同元素
        ++rank[y];
}

按秩合并其实并不能和路径压缩一起使用，因为路径压缩会破坏其秩的大小

扩展

并查集也可以应用在最小生成树算法中，其中一个比较经典的算法：kruskal算法就用到了并查集的辅助。这方面可以参考其他资料，这里不做过多的展开

练习

• 洛谷 P1551 亲戚

• 洛谷 P3958 奶酪

所以，并查集你应该掌握了，下课！