test/data_structure/rollback_union_find.test.cpp

• View this file on GitHub
• Last update: 2025-11-15 20:52:05+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_unionfind

Depends on

• Rollback Union Find (Rollback付きUnion Find) (data_structure/rollback_union_find.hpp)
• template/constant.hpp
• template/include.hpp
• template/macro.hpp
• 提出用テンプレート (template/template.hpp)
• template/type_alias.hpp
• Choose Minimum / Maximum (utility/choose_min_max.hpp)
• utility/set_io.hpp

Required by

• test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#include "../../data_structure/rollback_union_find.hpp"
#include "../../template/template.hpp"

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<vector<int>> g(Q + 1);
    vector<int> t(Q), k(Q), u(Q), v(Q);
    rep (i, 0, Q) {
        cin >> t[i] >> k[i] >> u[i] >> v[i];
        g[k[i] + 1].emplace_back(i + 1);
    }

    RollbackUnionFind uf(N);
    vector<bool> ans(Q);

    auto dfs = [&](auto& self, int now) -> void {
        now--;

        if (now != -1) {
            if (t[now] == 0) {
                uf.merge(u[now], v[now]);
            } else {
                ans[now] = uf.same(u[now], v[now]);
            }
        }

        for (int nex : g[now + 1]) {
            self(self, nex);
        }

        if (now != -1 && t[now] == 0) {
            uf.undo();
        }

        return;
    };

    dfs(dfs, 0);

    rep (i, 0, Q) {
        if (t[i] == 1) {
            cout << (ans[i] ? 1 : 0) << LF;
        }
    }

    return 0;
}

#line 1 "test/data_structure/rollback_union_find.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#line 2 "data_structure/rollback_union_find.hpp"

#line 2 "template/template.hpp"

/**
 * @author ku_senjan
 * @title 提出用テンプレート
 * @see https://github.com/kogetsu0728/ku-library
 */

#line 2 "template/constant.hpp"

#line 2 "template/include.hpp"

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
#line 2 "template/type_alias.hpp"

#line 4 "template/type_alias.hpp"

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

using ld = long double;

template <class T, bool REVERSE = false>
using heap = priority_queue<T, vector<T>, conditional_t<REVERSE, greater<T>, less<T>>>;
#line 5 "template/constant.hpp"

template <class T>
inline constexpr T INF = numeric_limits<T>::max() / 2;

inline constexpr array<int, 4> DY4 = {0, -1, 0, 1};
inline constexpr array<int, 4> DX4 = {1, 0, -1, 0};
inline constexpr array<int, 8> DY8 = {0, -1, -1, -1, 0, 1, 1, 1};
inline constexpr array<int, 8> DX8 = {1, 1, 0, -1, -1, -1, 0, 1};

inline constexpr char LF = '\n';
#line 2 "template/macro.hpp"

#line 5 "template/macro.hpp"

/**
 * @see https://trap.jp/post/1224/
 */

#ifdef LOCAL
inline constexpr bool IS_LOCAL = true;
#else
inline constexpr bool IS_LOCAL = false;
#endif

#define IF_LOCAL if constexpr (IS_LOCAL)

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define overload4(a, b, c, d, e, ...) e

#define rep1(i, a) for (ll i = 0; (i) < (ll)(a); ++(i))
#define rep2(i, a, b) for (ll i = (ll)(a); (i) < (ll)(b); ++(i))
#define rep3(i, a, b, c) for (ll i = (ll)(a); (i) < (ll)(b); (i) += (ll)(c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(i, a) for (ll i = (ll)(a); (i) >= 0; --(i))
#define rrep2(i, a, b) for (ll i = (ll)(a); (i) >= (ll)(b); --(i))
#define rrep3(i, a, b, c) for (ll i = (ll)(a); (i) >= (ll)(b); (i) -= (ll)(c))
#define rrep(...) overload4(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#line 13 "template/template.hpp"

#line 2 "utility/choose_min_max.hpp"

/**
 * @title Choose Minimum / Maximum
 */

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }

    return false;
}

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}
#line 2 "utility/set_io.hpp"

#line 4 "utility/set_io.hpp"

void set_io(int d = 16) {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(d);

    return;
}
#line 4 "data_structure/rollback_union_find.hpp"

/**
 * @brief Rollback Union Find (Rollback付きUnion Find)
 */
class RollbackUnionFind {
  private:
    int n, comp;
    vector<int> par;
    stack<pair<int, int>> his;

  public:
    RollbackUnionFind() : RollbackUnionFind(0) {}
    RollbackUnionFind(int _n) : n(_n), comp(_n), par(_n, -1), his() {}

    int size() const { return comp; }
    int size(int x) const { return -par[leader(x)]; }

    int leader(int x) const {
        if (par[x] < 0) {
            return x;
        }

        return leader(par[x]);
    }

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

    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);

        his.emplace(x, par[x]);
        his.emplace(y, par[y]);

        if (x == y) {
            return false;
        }

        if (size(x) < size(y)) {
            swap(x, y);
        }

        comp--;
        par[x] += par[y];
        par[y] = x;

        return true;
    }

    bool undo() {
        if (his.empty()) {
            return false;
        }

        vector<int> x(2);
        rep (i, 0, 2) {
            auto [v, p] = his.top();
            his.pop();

            x[i] = v;
            par[v] = p;
        }

        if (x[0] != x[1]) {
            comp++;
        }

        return true;
    }

    void snapshot() {
        while (!his.empty()) {
            his.pop();
        }

        return;
    }

    void rollback() {
        while (undo())
            ;

        return;
    }

    vector<vector<int>> groups() const {
        vector<vector<int>> mem(n);
        vector<vector<int>> res;

        rep (i, 0, n) {
            mem[leader(i)].emplace_back(i);
        }

        rep (i, 0, n) {
            if (!mem[i].empty()) {
                res.emplace_back(mem[i]);
            }
        }

        return res;
    }
};
#line 5 "test/data_structure/rollback_union_find.test.cpp"

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<vector<int>> g(Q + 1);
    vector<int> t(Q), k(Q), u(Q), v(Q);
    rep (i, 0, Q) {
        cin >> t[i] >> k[i] >> u[i] >> v[i];
        g[k[i] + 1].emplace_back(i + 1);
    }

    RollbackUnionFind uf(N);
    vector<bool> ans(Q);

    auto dfs = [&](auto& self, int now) -> void {
        now--;

        if (now != -1) {
            if (t[now] == 0) {
                uf.merge(u[now], v[now]);
            } else {
                ans[now] = uf.same(u[now], v[now]);
            }
        }

        for (int nex : g[now + 1]) {
            self(self, nex);
        }

        if (now != -1 && t[now] == 0) {
            uf.undo();
        }

        return;
    };

    dfs(dfs, 0);

    rep (i, 0, Q) {
        if (t[i] == 1) {
            cout << (ans[i] ? 1 : 0) << LF;
        }
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	conchon_filliatre_tle_00	AC	154 ms	29 MB
g++	conchon_filliatre_tle_01	AC	153 ms	29 MB
g++	example_00	AC	5 ms	4 MB
g++	hand_00	AC	4 ms	4 MB
g++	max_random_00	AC	179 ms	29 MB
g++	max_random_01	AC	180 ms	29 MB
g++	max_random_02	AC	179 ms	29 MB
g++	max_random_03	AC	178 ms	29 MB
g++	max_random_04	AC	178 ms	29 MB
g++	random_00	AC	132 ms	22 MB
g++	random_01	AC	133 ms	23 MB
g++	random_02	AC	106 ms	19 MB
g++	random_03	AC	27 ms	7 MB
g++	random_04	AC	85 ms	16 MB

Back to top page