并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

并查集支持两种操作：

• 并（合并）：将两个集合合并。
• 查（查询）：查找元素属于哪个集合，两个元素是否属于同一个集合。

基础并查集

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

vector<int> f, siz;
void init(int n) {
    f.resize(n + 1);
    iota(f.begin(), f.end(), 0);
    siz.assign(n + 1, 1);
}

查找

我们需要沿着树向上移动，直至找到根节点。

int find(int x) {
    while (f[x] != x) {
        x = f[x];
    }
    return x;
}

因为我们只关注整个集合，而不需要关注集合内的情况。查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点即可。

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    f[y] = x;
    siz[x] += siz[y];
}

完整代码

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        f[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }
};

可撤销并查集

顾名思义，就是可以撤销的并查集（但是不能重做）。

我们需要记录每一次的合并，在回滚的时候进行逆向操作即可。

需要注意的是，可撤销并查集不能使用路径压缩，否则会导致撤销错误。

完整代码

struct DSU {
    vector<int> f, siz;
    vector<array<int, 2>> his;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

    int find(int x) {
        while (f[x] != x) {
            x = f[x];
        }
        return x;
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (siz[x] < siz[y]) swap(x, y);
        his.push_back({x, y});
        f[y] = x;
        siz[x] += siz[y];
    }

    int time() {
        return his.size();
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }

    void revert(int tm) {
        while (his.size() > tm) {
            auto [x, y] = his.back();
            his.pop_back();
            f[y] = y;
            siz[x] -= siz[y];
        }
    }
};

带删除并查集

普通的并查集无法支持删除操作，是因为删除一个节点的时候，不可避免地会将以它为根的子树上所有节点都删除。所以我们可以建立虚点，让其代表这个集合，并且保证只有虚点有孩子节点，这样删除节点时就不会影响到其他节点了。