可撤销并查集
cpp
struct DSU{
vector<pair<int&,int>> his;
vector<int> par,siz;
int tot=0;
DSU(){}
DSU(int n){init(n);}
void set(int &a,int b){
his.push_back({a,a});
a=b;
}
void init(int n){
par.resize(n);
siz.assign(n,1);
iota(par.begin(),par.end(),0);
his.clear();
}
int find(int x){
return par[x]==x?x:find(par[x]);
}
bool merge(int x,int y,int op=1){
x=find(x),y=find(y);
if(x==y)return false;
if(siz[x]<siz[y])swap(x,y);
if(op){
set(par[y],x);
set(siz[x],siz[x]+siz[y]);
}
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
void rollback(int t=0){
while(his.size()>t){
auto [x,y]=his.back();
x=y;
his.pop_back();
}
}
};