前言
与 可持久化并查集 一起食用,效果更佳。
前置知识:并查集以及并查集的按秩合并优化。
例题引入
你需要维护一棵 \(n\) 个点的动态森林,初始时是 \(n\) 个散点,有 \(q\) 个操作,支持:
1 u v
,连边 \((u,v)\)。2 u v
查询 \(u,v\) 之间是否连通,连通输出Yes
,否则输出No
。3
撤销上一个 \(1\) 操作。保证存在被撤销的操作。
\(1 \leq n,q \leq 2 \times 10^6\)
请大家想一想这一道题的 \(O(n+q\log n)\) 的 在线 做法。
思路
可持久化并查集?复杂度多一个 \(\log\)。
现在我给大家介绍一个 \(O(1)\) 撤销,\(O(\log n)\) 合并,\(O(\log n)\) 查连通性的并查集——可撤销并查集。
首先,我们需要确保每一次合并操作时只会修改常数次 \(\operatorname{fa}\) 数组,这样子才能保证时间复杂度。这就意味着,我们不能路径压缩(应为 \(\operatorname{fa}\) 数组修改次数期望 \(O(\log n)\),复杂度未保证)。所以我们只能按秩合并。这里使用子树大小 \(\operatorname{siz}\) 为秩。
然后,用两个栈来维护每一次合并时修改前的 \(\operatorname{fa}\) 和 \(\operatorname{siz}\) ,然后撤销的时后用栈顶来还原,最后弹栈即可。
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
int fa[20000005],siz[20000005];
struct UndoObject{
int pos,val;
UndoObject(int p,int v){
pos=p,val=v;
}
};
stack<UndoObject> undo_sz,undo_fa;
int find(int x){
if(fa[x]==x)return x;
else return find(fa[x]);
}
void merge(int u,int v){
int x=find(u),y=find(v);
if(x==y)return;
if(siz[x]<siz[y]){
swap(x,y);
}
undo_sz.push(UndoObject(x,siz[x]));
siz[x]+=siz[y];
undo_fa.push(UndoObject(y,fa[y]));
fa[y]=x;
}
void undo(){
fa[undo_fa.top().pos]=undo_fa.top().val;
undo_fa.pop();
siz[undo_sz.top().pos]=undo_sz.top().val;
undo_sz.pop();
}
signed main(){
ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
cin>>q;
while(q--){
int op,u,v;
cin>>op;
if(op==1){
cin>>u>>v;
merge(u,v);
}
else if(op==2){
cin>>u>>v;
cout<<(find(u)==find(v)?"Yes":"No")<<'\n';
}
else{
undo();
}
}
return 0;
}
标签:log,int,查集,撤销,fa,笔记,operatorname
From: https://www.cnblogs.com/zheyuanxie/p/revocable-union-find.html