【模板】可持久化并查集(Persistent DSU) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

struct Op {
    int type, a, b;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Op> ops(m + 1);
    vector<vector<int>> tree(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> ops[i].type;
        if (ops[i].type == 2) {
            cin >> ops[i].a;
            tree[ops[i].a].push_back(i);
        } else {
            cin >> ops[i].a >> ops[i].b;
            tree[i - 1].push_back(i);
        }
    }
    vector<int> p(n + 1), sz(n + 1, 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) {
        while (p[x] != x) x = p[x];
        return x;
    };
    vector<int> ans(m + 1, -1);
    struct Frame {
        int u, idx, ru, rv;
    };
    vector<Frame> stk;
    stk.push_back({0, 0, 0, 0});
    while (!stk.empty()) {
        auto& f = stk.back();
        int u = f.u;
        if (f.idx == 0 && u > 0) {
            if (ops[u].type == 1) {
                int ru = find(ops[u].a), rv = find(ops[u].b);
                if (ru != rv) {
                    if (sz[ru] > sz[rv]) swap(ru, rv);
                    p[ru] = rv;
                    sz[rv] += sz[ru];
                    f.ru = ru;
                    f.rv = rv;
                }
            } else if (ops[u].type == 3) {
                ans[u] = (find(ops[u].a) == find(ops[u].b)) ? 1 : 0;
            }
        }
        if (f.idx < (int)tree[u].size()) {
            int v = tree[u][f.idx++];
            stk.push_back({v, 0, 0, 0});
        } else {
            if (f.ru != 0) {
                p[f.ru] = f.ru;
                sz[f.rv] -= sz[f.ru];
            }
            stk.pop_back();
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (ops[i].type == 3) cout << ans[i] << "\n";
    }
    return 0;
}