verify/LC-PersistentUnionfind.test.cpp

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

Depends on

• Library/Common.hpp
• Rollback Union-Find - Rollback 可能 Union-Find (Library/DataStructure/RollbackUnionFind.hpp)

Code

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

#include "../Library/DataStructure/RollbackUnionFind.hpp"

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    using qs = tuple<int, int, int, int>;
    vector<vector<qs>> G(Q + 1);
    for(int i = 1; i <= Q; ++i){
        int t, k, u, v; cin >> t >> k >> u >> v, ++k;
        G[k].push_back({t, i, u, v});
    }

    RollbackUnionFind uf(N);
    vector<int> ans(Q + 1, -1);
    auto dfs = [&](auto self, const qs &query) -> void {
        auto [t, i, u, v] = query;
        if(t == 1){
            ans[i] = uf.Same(u, v);
        }
        else{
            if(t == 0) uf.Unite(u, v);
            for(auto nquery : G[i]) self(self, nquery);
            if(t == 0) uf.Undo();
        }
    };
    dfs(dfs, {-1, 0, 0, 0});
    for(auto a : ans){
        if(a != -1) cout << a << '\n';
    }
}

#line 1 "verify/LC-PersistentUnionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/RollbackUnionFind.hpp"

class RollbackUnionFind{
    public:
    RollbackUnionFind(size_t n) : data_(n, -1), record_(0){}

    int Find(const int k) const {
        if(data_[k] < 0) return k;
        return Find(data_[k]);
    }

    bool Same(const int x, const int y) const {
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        history_.push({x, data_[x]});
        history_.push({y, data_[y]});
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    int Size(const int k) const {
        return -data_[Find(k)];
    }
    
    vector<vector<int>> Group() const {
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    void Record(){
        record_ = history_.size();
    }

    void Undo(){
        auto [y, dy] = history_.top();
        history_.pop();
        data_[y] = dy;
        auto [x, dx] = history_.top();
        history_.pop();
        data_[x] = dx;
    }

    void Rollback(){
        int state = record_;
        while(state < (int)history_.size()) Undo();
    }
    
    private:
    vector<int> data_;
    stack<pair<int, int>> history_;
    int record_;
};
#line 4 "verify/LC-PersistentUnionfind.test.cpp"

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    using qs = tuple<int, int, int, int>;
    vector<vector<qs>> G(Q + 1);
    for(int i = 1; i <= Q; ++i){
        int t, k, u, v; cin >> t >> k >> u >> v, ++k;
        G[k].push_back({t, i, u, v});
    }

    RollbackUnionFind uf(N);
    vector<int> ans(Q + 1, -1);
    auto dfs = [&](auto self, const qs &query) -> void {
        auto [t, i, u, v] = query;
        if(t == 1){
            ans[i] = uf.Same(u, v);
        }
        else{
            if(t == 0) uf.Unite(u, v);
            for(auto nquery : G[i]) self(self, nquery);
            if(t == 0) uf.Undo();
        }
    };
    dfs(dfs, {-1, 0, 0, 0});
    for(auto a : ans){
        if(a != -1) cout << a << '\n';
    }
}

Back to top page