# 可持久并查集

前置知识:主席树、可持久化数组

作用:保存历史的集合版本,查询过去版本

空间复杂度 >=(klog (n)+2log(n)-1) [一般开 40 倍原空间]

详细讲解

# 大致过程

将 fa 数组和 dep 数组可持久化,fa 数组就有了各个版本不同的值,如果开结构体的话只需要将 fa 定义成结构体类型,因为两个数组可持久化后下标是相同的,需要注意的是不能路径压缩,一定要按秩合并!

# 题目

洛谷模板

image-20210426204636666

# 题意

给定 n 个集合,每一个集合初始只有自己一个数,接下来 m 次操作,每次操作有三种选择,合并 a 和 b,回到 k 版本,询问 a 和 b 是否属于一个集合

# 解法

将 fa 数组和 dep 数组可持久化,需要注意的是一定不能路径压缩,因为每次要保存版本,只是拉出来一条链,压缩路径的话就会影响其他版本的 fa 数组值,例如现在高版本压缩了一次路径,低版本的 fa 数组值被改变了,之后查询低版本时就会出错!如果没有了路径压缩那么时间就会慢很多,所以一定要按秩合并来优化一下,为什么按秩合并会快一点呢?

image-20210426213034161

看这个图,倘若询问 2 和 4 是否在一个集合,第一个畸形图就需要多往上走两步,而第二个图就可以省下些时间。

# CODE

#include <bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3,"Ofast","inline")
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int ls,rs,val;
}fa[MAXN*40];  
int dep[MAXN*40],rt[MAXN*40];
int n,m,op,a,b,tot,k;
int build(int l,int r){  
	int root=++tot;
	if(l==r){
		fa[root].val=l;  // 初始 fa 数组值为本身
		return root;
	}
	int mid=(l+r)>>1;
	fa[root].ls=build(l,mid);
	fa[root].rs=build(mid+1,r);
	return root;
}
int query(int nod,int l,int r,int x){  // 查询 x 在这个版本的 fa 数组下标
	if(l==r) return nod;
	int mid=l+r>>1;
	if(x<=mid) return query(fa[nod].ls,l,mid,x);  // 在左子树上
	else return query(fa[nod].rs,mid+1,r,x);
}
int find(int nod,int x){
	int now=query(nod,1,n,x);  // 查询 x 点在这个版本中 fa 数组的下标
	if(fa[now].val==x) return now;  // 如果 x 的父亲值就是 x 说明 x 就是祖先
	return find(nod,fa[now].val);  // 否则就继续找
}
int remerge(int pre,int l,int r,int x,int y){
	int root=++tot;
	fa[root]=fa[pre];  // 合并时需要创建一个新版本
	if(l==r){
		fa[root].val=y;  // 更新这个位置的父亲值
		return root;
	}
	int mid=l+r>>1;
	if(x<=mid) fa[root].ls=remerge(fa[pre].ls,l,mid,x,y);
	else fa[root].rs=remerge(fa[pre].rs,mid+1,r,x,y);
	return root;
}
int main(){
	ios;
	cin>>n>>m;
	rt[0]=build(1,n);  // 初始化 fa 数组
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>a>>b;
			rt[i]=rt[i-1];  // 一定不能少了这一句,之前我就是想着 remerge 里面已经创建当前版本了,所以这一句没必要,但是如果两个点已经在一个集合里了,下面的 if 就不会执行,当前版本就没有保存
			int x=find(rt[i],a),y=find(rt[i],b);  // 查询 a 和 b 在当前版本的祖先
			if(fa[x].val!=fa[y].val){  
				if(dep[x]>dep[y]) swap(x,y);  // 按秩合并
				rt[i]=remerge(rt[i-1],1,n,fa[x].val,fa[y].val);  // 保存版本
				if(dep[x]==dep[y]) dep[y]++;  // 如果两个集合高度相同的话,合并后父集合高度要加一
			}
		}
		else if(op==2){
			cin>>k;
			rt[i]=rt[k];  // 回到 k 版本
		}
		else if(op==3){
			cin>>a>>b;
			rt[i]=rt[i-1];  // 新建版本
			int fx=find(rt[i],a),fy=find(rt[i],b);  // 查询
			if(fx==fy) cout<<1<<'\n';
			else cout<<0<<'\n';
		}
	}
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝