并查集本质上是维护一个森林，初始时森林里每个点是一个集合，之后将集合合并，查找一个点所在集合的代表元素，将两个集合的代表元素进行合并。使用时不要忘记初始化！
在一般情况下，可以使用路径压缩与按秩合并或启发式合并。
struct DSU{
int f[N<<1],sz[N<<1],rk[N];
inline void init(int n){
//for(int i=1;i<=n;i++)f[i]=i,sz[i]=1;
for(int i=1;i<=n;i++)f[i]=i+n,sz[i]=rk[i]=0;/*每个点预先设置一个父亲，这样删除时就不会有被删除节点是根的情况*/
for(int i=n+1;i<=2*n;i++)f[i]=i,sz[i]=1,rk[i]=0;
}
int find(int x){/*递归版find*/
return x==f[x]?x:f[x]=find(f[x]);/*路径压缩*/
}
inline int get(int x){/*非递归版find*/
while(x!=f[x])x=f[x]=f[f[x]];
return x;
}
inline bool unity(int x,int y){/*将y集合合并到x所在集合*/
x=find(x),y=find(y);
if(x==y)return false;
f[y]=x;
return true;
}
inline bool merge(int x,int y){
x=find(x),y=find(y);/*找到代表元素*/
if(x==y)return false;/*已经在一个集合里了，合并失败*/
if(sz[x]<sz[y])x^=y^=x^=y;/*强制x较大y较小，启发式合并，若需要严格的祖先关系则不可行*/
f[y]=x,sz[x]+=sz[y];/*y合并给x*/
return true;/*合并成功*/
}
inline bool unite(int x,int y){/*按秩合并*/
x=find(x),y=find(y);
if(x==y)return false;
if(rk[x]<rk[y])x^=y^=x^=y;/*钦定x秩较大*/
f[y]=x,rk[x]+=rk[x]==rk[y];/*秩相等则增加秩*/
return true;
}
inline void move(int x,int y){/*将x移动到y所在的集合*/
int fx=find(x),fy=find(y);
if(fx==fy)return;
f[x]=fy,sz[fx]--,sz[fy]++;
}
inline void del(int x){/*删除x结点*/
f[x]=x;/*父亲设置为自己*/
sz[find(x)]--;
}
}d;
如果需要的删除操作是和连通性有关的，那么可以考虑倒叙进行操作，将删边转化为加边。
在扩展域并查集中，一般不使用对合并的优化，因为扩展域要求有严格的关系。
可撤销并查集，用线段树进行在时间轴上的分治，在回溯时需要撤销操作，故不能使用路径压缩。
给出每条边出现和消失的时刻，问在i时间段内这张图是否是连通图。注意时刻和时间段的区别。
struct SDSU{
struct tree{
int l,r;
vector<int>v;
}t[N<<2];
#define lc p<<1
#define rc p<<1|1
int f[N],rk[N];
pair<int,int>e[N];/*每条边*/
stack<pair<int,int>>s;/*撤销操作需要的栈*/
inline void init(int n){
for(int i=1;i<=n;i++)f[i]=i,rk[i]=0;
}
inline int find(int x){
while(x^f[x])x=f[x];/*循环找代表元素*/
return x;
}
inline void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(rk[x]<rk[y])x^=y^=x^=y;/*强制x的秩较大*/
s.push({y/*修改父亲的点*/,rk[x]==rk[y]/*修改的秩*/});
f[y]=x,rk[x]+=rk[x]==rk[y];
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
}
void update(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r)return t[p].v.push_back(x),void();/*在时间轴[l,r]内，存在时间节点x，即第x条边*/
int mid=t[p].l+t[p].r>>1;
if(l<=mid)update(lc,l,r,x);
if(mid<r)update(rc,l,r,x);
}
void solve(int p){
int ok=1,last=s.size();/*记录操作数*/
for(auto x:t[p].v){
int a=find(e[x].first),b=find(e[x].second);
if(a==b){/*如果一条边的两端在同一个集合中，那么不是二分图*/
for(int k=t[p].l;k<=t[p].r;k++)cout<<"No\n";
ok=0;
break;
}
merge(e[x].first+n,e[x].second);/*对应扩展域进行合并*/
merge(e[x].second+n,e[x].first);
}
if(ok){
if(t[p].l==t[p].r)cout<<"Yes\n";
else solve(lc),solve(rc);
}
while(s.size()>last){/*撤销之前的操作*/
rk[f[s.top().first]]-=s.top().second;/*修改被合并结点合并到的父节点的秩*/
f[s.top().first]=s.top().first;/*断开连接*/
s.pop();
}
}
}s;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
s.init(n+n);
s.build(1,1,k);
for(int i=1;i<=m;i++){
int l,r;
cin>>s.e[i].first>>s.e[i].second>>l>>r;
s.update(1,l+1,r,i);
}
s.solve(1);
return 0;
}
给出k个集合和该集合内的边，询问去掉该集合后图是否联通。将集合看做时间，每条边存在的时间就是不包含该边的集合。
struct SDSU{
struct tree{
int l,r;
vector<int>v;
}t[N<<2];
#define lc p<<1
#define rc p<<1|1
int f[N],sz[N];
pair<int,int>e[N];/*每条边*/
stack<pair<int,int>>s;/*撤销操作需要的栈*/
inline void init(int n){
for(int i=1;i<=n;i++)f[i]=i,sz[i]=1;
}
inline int find(int x){
while(x^f[x])x=f[x];/*循环找代表元素*/
return x;
}
inline void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(sz[x]<sz[y])x^=y^=x^=y;/*强制x较大*/
s.push({y/*修改父亲的点*/,sz[y]/*修改的集合大小*/});
f[y]=x,sz[x]+=sz[y];
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
}
void update(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r)return t[p].v.push_back(x),void();/*在时间轴[l,r]内，存在时间节点x，即第x条边*/
int mid=t[p].l+t[p].r>>1;
if(l<=mid)update(lc,l,r,x);
if(mid<r)update(rc,l,r,x);
}
void solve(int p){
int last=s.size();
for(auto x:t[p].v)merge(e[x].first,e[x].second);
if(t[p].l==t[p].r)ans[t[p].l]=sz[find(1)]==n;/*在当前时间内图是连通图*/
else solve(lc),solve(rc);
while(s.size()>last){
sz[f[s.top().first]]-=s.top().second;/*复原被合并结点的父亲的大小*/
f[s.top().first]=s.top().first;
s.pop();
}
}
}s;
struct node{
int s,t,id;
}op[N*20];
int last[N];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
s.init(n);
for(int i=1;i<=m;i++)cin>>s.e[i].first>>s.e[i].second,last[i]=1;/*每条边初始存在是1时刻*/
cin>>k;
s.build(1,1,k);
int p=0;
for(int i=1;i<=k;i++){
int c;cin>>c;
for(int j=1;j<=c;j++){
int x;cin>>x;
op[++p]={last[x],i-1,x};/*该集合i中的边x存在的时间是上一次到i-1*/
last[x]=i+1;/*先假设下一次可能出现*/
}
}
for(int i=1;i<=m;i++)if(last[i]!=k+1)op[++p]={last[i],k,i};/*自上一次出现后一直存在到最后*/
for(int i=1;i<=p;i++)if(op[i].s<=op[i].t)s.update(1,op[i].s,op[i].t,op[i].id);
s.solve(1);
for(int i=1;i<=k;i++)cout<<(ans[i]?"Connected\n":"Disconnected\n");
return 0;
}
共有k种颜色，初始时无色透明，合法状态为仅炮流k种颜色种的任何一种颜色的边，图都是二分图，q次将第e[i]条边染色成c[i]，只有当执行后合法才会执行，判断是否会被执行。一个可撤销并查集变成了k个，对于一条边的两次染色x,y，染色区间为[x+1,y-1]，颜色只有染上了是x染色时的颜色，和没染上时上一次的颜色，直接假定染色成功，递归到叶子进行判断，若没有成功则撤销操作，并查集维护判断奇环，在每次加入这条边的时间点判断能够成功修改，确定接下来一段时间它的颜色。
struct SDSU{
struct tree{
int l,r;
vector<int>v;
}t[N<<2];
int f[K][N<<1],rk[K][N<<1];
pair<int,int>e[N];
struct stk{
int c,x,y;
};
stack<stk>s;
#define lc p<<1
#define rc p<<1|1
inline void init(int n,int k){
for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)f[j][i]=i;
}
inline int find(int p,int x){
while(x^f[p][x])x=f[p][x];
return x;
}
inline void merge(int p,int x,int y){
x=find(p,x),y=find(p,y);
if(x==y)return;
if(rk[p][x]<rk[p][y])x^=y^=x^=y;
s.push({p,y,rk[p][x]==rk[p][y]});
f[p][y]=x,rk[p][x]+=rk[p][x]==rk[p][y];
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
}
void update(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r)return t[p].v.push_back(x),void();
int mid=t[p].l+t[p].r>>1;
if(l<=mid)update(lc,l,r,x);
if(mid<r)update(rc,l,r,x);
}
void solve(int p){
int last=s.size();
for(auto x:t[p].v)merge(c[x],e[a[x]].first+n,e[a[x]].second),merge(c[x],e[a[x]].second+n,e[a[x]].first);/*对应反集进行合并，x是第x次操作，对应第e[a[x]]条边*/
if(t[p].l==t[p].r){
if(find(c[t[p].l],e[a[t[p].l]].first)==find(c[t[p].l],e[a[t[p].l]].second))cout<<"NO\n",c[t[p].l]=la[a[t[p].l]];/*修改失败，那么这第t[p].l次操作就是上一次对第a[t[p].l]条边操作la[a[t[p].l]]的结果*/
else cout<<"YES\n",la[a[t[p].l]]=c[t[p].l];/*修改成功，更新上一次对第a[t[p].l]条边的修改结果，颜色为c[t[p].l]*/
}
else solve(lc),solve(rc);
while(s.size()>last){
rk[s.top().c][f[s.top().c][s.top().x]]-=s.top().y;
f[s.top().c][s.top().x]=s.top().x;
s.pop();
}
}
}s;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>k>>q;
s.build(1,1,q);
s.init(n+n,k);
for(int i=1;i<=m;i++)cin>>s.e[i].first>>s.e[i].second,la[i]=q+1;
for(int i=1;i<=q;i++)cin>>a[i]>>c[i];/*将第e[a[i]]条边染色成c[i]*/
for(int i=q;i;i--){
if(i<la[a[i]]-1)/*本次操作小于上一次操作-1*/s.update(1,i+1,la[a[i]]-1,i);/*本次操作对应的时间段为[i+1,la[a[i]]-1]*/
la[a[i]]=i;/*更新上一次对第a[i]条边的操作*/
}
for(int i=1;i<=m;i++)la[i]=0;
s.solve(1);
return 0;
}
连边和删边两种操作，询问所有联通块大小的乘积。线段树分治维护可撤销并查集。
struct UDSU{
int fa[N],sz[N],res=1;
map<pair<int,int>,int>mp;
stack<int>ans;
inline void init(int n){for(int i=1;i<=n;i++)sz[fa[i]=i]=1;res=1;}
inline int find(int x){while(x^fa[x])x=fa[x];return x;}
pair<int,int>Link(const pair<int,int>&pii){
int x=find(pii.first),y=find(pii.second);
if(x==y)return {0,0};
if(sz[x]>sz[y])swap(x,y);
ans.push(res);
res=res*inv[sz[x]]%mod*inv[sz[y]]%mod*(sz[x]+sz[y])%mod;
fa[x]=y;sz[y]+=sz[x];
return {x,y};
}
inline void cut(const pair<int,int>&pii){
int x=pii.first,y=pii.second;
if(!x&&!y)return;
//res=res*inv[sz[y]]%mod;
fa[x]=x;
sz[y]-=sz[x];
res=ans.top();ans.pop();
//res=res*sz[x]%mod*sz[y]%mod;
}
struct tree{
int l,r;
vector<pair<int,int>>v;
}t[N<<2];
#define lc p<<1
#define rc p<<1|1
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void update(int p,int l,int r,const pair<int,int>&pii){
if(l<=t[p].l&&t[p].r<=r)return t[p].v.push_back(pii),void();
int mid=t[p].l+t[p].r>>1;
if(l<=mid)update(lc,l,r,pii);
if(mid<r)update(rc,l,r,pii);
}
void solve(int p,int l,int r){
for(auto&x:t[p].v)x=Link(x);//要引用啊！
if(l==r)an[l]=res;
else{
int mid=l+(r-l>>1);
solve(lc,l,mid);
solve(rc,mid+1,r);
}
for(int i=t[p].v.size()-1;i>=0;i--)cut(t[p].v[i]);
}
inline void add(int a,int b,int id){if(a>b)swap(a,b);mp[{a,b}]=id;}
inline void del(int a,int b,int id){if(a>b)swap(a,b);update(1,mp[{a,b}],id-1,{a,b}),mp[{a,b}]=0;}
inline void pre(int m){for(auto it:mp)if(it.second)update(1,it.second,m,it.first);}
}udsu;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
udsu.init(n);
inv[1]=1;
udsu.build(1,1,m);
for(int i=2;i<=n;i++)inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
for(int i=1;i<=m;i++){
int op,a,b;cin>>op>>a>>b;
if(op==1)udsu.add(a,b,i);
if(op==2)udsu.del(a,b,i);
}
udsu.pre(m);
udsu.solve(1,1,m);
for(int i=1;i<=m;i++)cout<<an[i]<<'\n';
return 0;
}
可持久化并查集，其实是可持久化线段树的巧妙应用，用两个主席树维护fa和size，在合并时进行对应的修改。
struct PersistentSegmentTree{
struct tree{
int l,r,v;
}t[N<<5];
int tot,root[N],a[N];
#define l(p) (t[p].l)
#define r(p) (t[p].r)
#define v(p) (t[p].v)
void build(int&p,int l,int r){
p=++tot;
if(l==r){
v(p)=a[l];
return;
}
int mid=l+r>>1;
build(l(p),l,mid);
build(r(p),mid+1,r);
}
void modify(int&p,int q,int l,int r,int x,int v){
p=++tot;
t[p]=t[q];
if(l==r){
v(p)=v;
return;
}
int mid=l+r>>1;
if(x<=mid)modify(l(p),l(q),l,mid,x,v);
else modify(r(p),r(q),mid+1,r,x,v);
}
int query(int p,int l,int r,int x){
if(l==r)return v(p);
int mid=l+r>>1;
if(x<=mid)return query(l(p),l,mid,x);
else return query(r(p),mid+1,r,x);
}
}fa,sz;
struct PersistentDSU{
inline void init(int n){
for(int i=1;i<=n;i++)fa.a[i]=i,sz.a[i]=1;
fa.build(fa.root[0],1,n);
sz.build(sz.root[0],1,n);
}
inline int find(int p,int x){
while(true){
int f=fa.query(fa.root[p],1,n,x);
if(f==x)return x;
x=f;
}
}
inline void merge(int p,int x,int y){
x=find(p,x),y=find(p,y);
if(x==y)return;
int a=sz.query(sz.root[p],1,n,x),b=sz.query(sz.root[p],1,n,y);
if(a<b)swap(x,y),swap(a,b);
fa.modify(fa.root[p],fa.root[p],1,n,y,x);
sz.modify(sz.root[p],sz.root[p],1,n,x,a+b);
}
}pdsu;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
pdsu.init(n);
for(int i=1;i<=m;i++){
int op,x,y;
cin>>op>>x;
fa.root[i]=fa.root[i-1];
sz.root[i]=sz.root[i-1];
if(op==1)cin>>y,pdsu.merge(i,x,y);
else if(op==2)fa.root[i]=fa.root[x],sz.root[i]=sz.root[x];
else cin>>y,cout<<(pdsu.find(i,x)==pdsu.find(i,y)?1:0)<<'\n';
}
return 0;
}