并查集

并查集

并查集是一种树形数据结构，经常用于处理一些集合之间的操作，例如元素查找、集合合并等

不同集合在并查集中以不同的树来表示，一般每棵树的根节点会作为当前集合的代表元

想要查询两个元素是否在同一集合里，只需要比较两个元素所在集合的代表元是否相同即可

初始化

cont int MAX = 1001; // 最大元素个数

int fa[MAX]; // 记录每个元素由谁代表
void init(int n) {
    // 初始化每个元素的代表元都是自己
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

集合合并

先找到x,y对应的代表元

将其中一个代表元的fa指向另外一个

int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return find(fa[x]);
}
void union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

路径压缩

如果并查集在合并过程中形成了一条长链，则每次查找代表元都要花费大量的时间

为了缩短并查集中的路径，可以在查询的过程中，将沿途的每个节点的fa都设为集合代表元

int find(int x) {
    if (x == fa[x]) {
        return x;
    }
    fa[x] = find(fa[x]);
    return fa[x];
}
// 另一种写法
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

启发式合并

在合并集合的时候，将元素个数少的集合指向元素个数多的集合

void union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (size[fx] > size[fy])
        swap(fx, fy);
    fa[fx] = fy;
    size[fy] += size[fx];
}

按深度合并

在合并集合的时候，将深度较小的集合合并到深度较大的一方

在路径压缩的时候，有可能会破坏维护的深度值，但是算法总体复杂度不会变差

void union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (depth[fx] > depth[fy])
        swap(fx, fy);
    fa[fx] = fy;
    if (depth[fx] == depth[fy])
        depth[fy]++;
}