Disjoint-Set，也称Union-Find或Disjoint-Set-Union，是一种用于表示不相交集合的数据结构。并查集可用于解决像朋友圈这样的问题，即在一个相互可能为朋友的朋友圈里计算朋友圈的数目，以及判断两个人是否属于同一个朋友圈。

并查集支持以下两种操作：

合并：将两个不相交的集合合并为一个。
查询：查询两个元素是否在同一个集合中。

初始版

简单的并查集体结构的设计如下：

class DSU {
    vector<int> parent;
public:
    DSU(int n) : parent(n) {
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if(parent[x] == x) {
            return x;
        } else {
            return find(parent[x]);
        }
    }

    void merge(int x, int y) { // 将y的parent设置为x的parent
        parent[find(y)] = parent[find(x)];
    }
};

下面的过程演示了并查集的工作流程：

draw.io

Diagram attachment access error: cannot display diagram

注意，在merge(2, 3)时，需要递归找到2的根结点1，再把3合并到1上。

路径压缩

上面的设计存在一个问题，就是最后形成的并查集树可能层数很高，甚至是一个链，比如下面的操作：

DSU dsu(4);
merge(2, 1);
merge(3, 1);
merge(4, 3);

生成的树结构如下：

draw.io

Diagram attachment access error: cannot display diagram

随着链越来越长，查询结点的根结点也会越来越耗时。

解决办法就是路径压缩，思路是在每次查询一个结点的根节点时，将沿途的结点的父结点全部更新一遍，需要修改的点如下：

int find(int x) {
    if(parent[x] == x) {
        return x;
    } else {
        parent[x] = find(parent[x]);
        return parent[x];
    }
}

按秩合并

用于合并两颗树时，确定以哪个树作为根。

页面树结构

并查集

初始版

路径压缩

按秩合并