可撤销并查集学习笔记

标签：log int 查集 撤销 fa 笔记 operatorname

前言

与 可持久化并查集 一起食用，效果更佳。

前置知识：并查集以及并查集的按秩合并优化。

例题引入

你需要维护一棵 \(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