• 可撤销并查集

struct RollbackDSU {
    std::vector<int> fa, siz;
    struct op {
        int u, v;
    };
    std::vector<op> his;

    RollbackDSU(int n) : fa(n + 1), siz(n + 1, 1) { std::iota(fa.begin(), fa.end(), 0); }

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

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

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) std::swap(x, y);
        siz[x] += siz[y];
        fa[y] = x;
        his.push_back({x, y});
        return true;
    }

    int snapshot() const { return his.size(); }

    void rollback(int snap) {
        while ((int)his.size() > snap) {
            auto& [u, v] = his.back();
            siz[u] -= siz[v];
            fa[v] = v;
            his.pop_back();
        }
    }
};