src/dsu/dsu_rollback.hpp

View this file on GitHub
Last update: 2025-12-30 15:03:15+09:00
Include: #include "src/dsu/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(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/dsu/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;
    }
};