本笔记内容来源于算法基础课

并查集

作用：

1. 将两个集合合并
2. 询问两个元素是否在一个集合当中

时间复杂度为$O(1)$

基本原理

用树的形式来维护集合

每棵树的根节点代表集合的编号，每个节点都存储其父节点

查询集合：返回节点所在树的根节点
合并集合：将一棵树的根节点指向另一棵树的根节点

优化思想

减少树的高度

路径压缩：在查询的过程中，将路径上的所有点都指向根节点
按秩合并：在合并的过程中，将较矮的树指向较高的树（不常考）

p[i] 代表节点i的父节点，等于i代表为根节点

初始化

void init() {
    for (int i = 1; i <= n; i++) p[i] = i;
}

查询集合（路径压缩优化）

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); // 使父节点等于的父节点的...直到等于根节点
    return p[x]; // 返回父节点
}

合并集合

void union(int a, int b) {
    p[find(a)] = find(b); // a的树的根节点的父节点等于b的树的根节点
}

扩展

维护额外信息

维护集合的大小

size[i] 代表根节点i的集合大小，非根节点无意义

初始化

void init() {
    for (int i = 1; i <= n; i++)  {
        p[i] = i;
        size[i] = 1; // 初始化集合大小
    }
}

合并集合

void union(int a, int b) {
    int x = find(a), y = find(b);
    if (x == y) return;
    p[x] = y; // a的树的根节点的父节点等于b的树的根节点
    size[y] += size[x]; // 注意是根节点改变记录的大小，而且要在合并之前进行调整

}

注意
在合并之前需要判断是否在同一个集合，否则大小记录会出错

if (find(a) != find(b)) union(a, b);

带权并查集

用于确定两两元素之间的关系

使用距离来代表关系，每两个节点之间的关系，可以由该两个节点到根节点之间的关系得到，因此维护每个点到根节点的距离

路径压缩：每个节点与根节点之间的距离进行更新

d[i] 代表节点i到父节点的距离

初始化

void init() {
    for (int i = 1; i <= n; i++)  {
        p[i] = i;
        d[i] = 0; // 全局变量自动初始化为0，可不写
    }
}

查询集合（路径压缩优化）

int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]); // 暂存根节点，直接赋值p[x]，会导致距离更新错误
        d[x] += d[p[x]]; // 距离加上父节点到根节点的距离
        p[x] = t // 指向根节点
    }
    return p[x]; // 返回父节点
}

注意
在进行合并操作，更新距离时需要额外将根节点提出，以防止根节点距离更新错误

int px = find(x), py = find(y);
p[px] = py;
d[px] = ...;

例题

Acwing 4075 使用并查集划分集合

Acwing 4420 求连通分量