题解 P3367 【【模板】并查集】

· · 题解

并查集板子题。平常的查找+路径压缩就能过掉了

但是为了提高题解通过率更好的优化，本蒟蒻提供一种优化新思路：按秩合并。

对于一个集合，秩指的就是这个集合中元素的个数。在并查集的合并操作中，如果我们将秩较小的集合合并到秩更大的集合上，那么比起将秩较大的集合合并到秩更小的集合上，在每一次查询操作中，前者总能花费更少的时间。

值得一提的是，按秩合并也被称为启发式合并。它是数据结构相关问题的一种重要思想，就是把“小的结构”合并到“大的结构”中，并且只增加“小的结构”的查询代价。所以在并查集中，我们把所有集合合并起来后，增加的总代价也不会超过N\log N。也就是说，单次查询的平均时间复杂度为\mathcal{O}(\log N)。

那么同时使用路径压缩和按秩合并的优化呢？如果我们这么做的话，单次查询操作的时间复杂度会变成一个奇怪的东西：\mathcal{O}(\alpha(N))。其中\alpha(N)为反阿克曼函数，它是一个比\log N增长得还要慢的函数。

就这么跟你形容吧：\forall N \le 2^{2^{10^{19279}}}，都有\alpha(N)\le 5。就问你快不快？

下面来看看代码：

#include <cstdio>

int n, m, fa[10010], size[10010];//size数组记录各集合的秩

int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);//路径压缩
}

void merge(int x, int y) {
    int X = get(x), Y = get(y);
    if (size[X] > size[Y]) {//比较两集合秩的大小，然后按秩合并
        fa[Y] = X;
        size[X] += size[Y];
    } else {
        fa[X] = Y;
        size[Y] += size[X];
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        size[i] = 1;//最开始每个集合的秩都是1
    }
    for (int i = 1; i <= m; i++) {
        int z, x, y;
        scanf("%d %d %d", &z, &x, &y);
        if (z == 1) merge(x, y);
        if (z == 2) {
            if (get(x) == get(y)) puts("Y");
            else puts("N");
        }
    }
    return 0;
}