src/dsu_rollback.hpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Include: #include "src/dsu_rollback.hpp"

Depends on

src/template.hpp

Code

#include "template.hpp"

struct dsu_rollback {
    vector<int> p;
    vector<pair<int, int>> st;
    dsu_rollback(int n): p(n, -1) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int size(int x) { return -p[leader(x)]; }
    int leader(int x) { return p[x] < 0 ? x : leader(p[x]); }
    int time() { return si(st); }
    void rollback(int t) {
        for(int i = time(); i-- > t;) p[st[i].first] = st[i].second;
        st.resize(t);
    }
    int merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b);
        st.push_back({a, p[a]});
        st.push_back({b, p[b]});
        p[a] += p[b];
        p[b] = a;
        return a;
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 2 "src/dsu_rollback.hpp"

struct dsu_rollback {
    vector<int> p;
    vector<pair<int, int>> st;
    dsu_rollback(int n): p(n, -1) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int size(int x) { return -p[leader(x)]; }
    int leader(int x) { return p[x] < 0 ? x : leader(p[x]); }
    int time() { return si(st); }
    void rollback(int t) {
        for(int i = time(); i-- > t;) p[st[i].first] = st[i].second;
        st.resize(t);
    }
    int merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b);
        st.push_back({a, p[a]});
        st.push_back({b, p[b]});
        p[a] += p[b];
        p[b] = a;
        return a;
    }
};