并查集是很常见的数据结构,通常我们合并两颗子树之后就没法拆开了,但是如果我们能够访问历史版本的并查集,那么就可以达到拆开的效果了。

学习可持久化并查集需要先学习并查集和可持久化数组~

如何实现并查集的可持久化?

对于并查集来说,最重要的就是father[]数组了,所以我们主要维护的就是father[]数组的可持久化。

并查集优化

并查集有两种最常见的优化方式。分别是路径压缩和按秩合并。

路径压缩

路径压缩是最常见的并查集优化方式了,路径压缩的效果就是将一颗子树的一些非root结点连接到root结点上,从一颗瘦高的树变成一颗矮胖的树,从而减少查找时间。写法也非常的简单。

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

但是对于可持久化并查集来说,还能否使用路径压缩呢?答案是最好别了,因为对于可持久化的数据结构来说,每操作一次就要生成一个新的版本,存在MLE的风险。

按秩合并

按秩合并需要记录下每颗子树的树高,在合并两颗子树时,将矮的子树挂在高的子树上,那么新的子树的最坏查询时间不会增大,也是常见的优化方式。

按秩合并在可持久化并查集常用,也是有必要的。

可持久化并查集的实现

参数

// 维护可持久化数组的结点,因为要维护father数组和dep数组,所以开辟了80倍空间
struct node {
	int l, r, val;
}tree[maxn * 40 * 2];

int rootfa[maxn], rootdep[maxn];
int cnt, tot;

可持久化数组

可持久化数组就没什么好说的,直接上板子

void build(int l, int r, int &now) {
	now = ++cnt;
	if (l == r) {
		tree[now].val = ++tot;	// tot达到fa[i] = i的效果
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, tree[now].l);
	build(mid+1, r, tree[now].r);
}

void modify(int l, int r, int pre, int &now, int pos, int val) {
	now = ++cnt;
	tree[now] = tree[pre];
	if (l == r) {
		tree[now].val = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(l, mid, tree[pre].l, tree[now].l, pos, val);
	else modify(mid+1, r, tree[pre].r, tree[now].r, pos, val);
}

int query(int l, int r, int now, int pos) {
	if (l == r) return tree[now].val;
	int mid = (l + r) >> 1;
	if (pos <= mid) return query(l, mid, tree[now].l, pos);
	else return query(mid+1, r, tree[now].r, pos);
}

并查集find()

find操作也非常的好写,注意不要路径压缩

// ver是版本号
int find(int ver, int x) {
	int fx = query(1, n, rootfa[ver], x);
	return fx == x ? x : find(ver, fx);
}

并查集merge()

merge操作使用按秩合并进行优化,需要注意的是,在合并时,当前版本是没有东西的,所以在操作时都要基于上一个版本。

void merge(int ver, int x, int y) {
	x = find(ver-1, x);	// 新版本还未操作,要从上一个版本找
	y = find(ver-1, y);
	if (x == y) {
		rootfa[ver] = rootfa[ver-1];
		rootdep[ver] = rootdep[ver-1];
	} else {
		int depx = query(1, n, rootdep[ver-1], x);
		int depy = query(1, n, rootdep[ver-1], y);
		if (depx < depy) {
			modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
			rootdep[ver] = rootdep[ver-1];
		} else if(depx > depy) {
			modify(1, n, rootfa[ver-1], rootfa[ver], y, x);
			rootdep[ver] = rootdep[ver-1];
		} else {
			modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
			modify(1, n, rootdep[ver-1], rootdep[ver], y, depy+1);
		}
	}
}

洛谷P3402

洛谷P3402是一道模板题

image-20200907090424700

// 样例输入
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

// 样例输出
1
0
1
// AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 2e5+5;

struct node {
	int l, r, val;
}tree[maxn * 40 * 2];

int rootfa[maxn], rootdep[maxn];
int cnt, tot;
int n, m;

void build(int l, int r, int &now) {
	now = ++cnt;
	if (l == r) {
		tree[now].val = ++tot;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, tree[now].l);
	build(mid+1, r, tree[now].r);
}

void modify(int l, int r, int pre, int &now, int pos, int val) {
	now = ++cnt;
	tree[now] = tree[pre];
	if (l == r) {
		tree[now].val = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(l, mid, tree[pre].l, tree[now].l, pos, val);
	else modify(mid+1, r, tree[pre].r, tree[now].r, pos, val);
}

int query(int l, int r, int now, int pos) {
	if (l == r) return tree[now].val;
	int mid = (l + r) >> 1;
	if (pos <= mid) return query(l, mid, tree[now].l, pos);
	else return query(mid+1, r, tree[now].r, pos);
}

int find(int ver, int x) {
	int fx = query(1, n, rootfa[ver], x);
	return fx == x ? x : find(ver, fx);
}

void merge(int ver, int x, int y) {
	x = find(ver-1, x);	// 新版本还未操作,要从上一个版本找
	y = find(ver-1, y);
	if (x == y) {
		rootfa[ver] = rootfa[ver-1];
		rootdep[ver] = rootdep[ver-1];
	} else {
		int depx = query(1, n, rootdep[ver-1], x);
		int depy = query(1, n, rootdep[ver-1], y);
		if (depx < depy) {
			modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
			rootdep[ver] = rootdep[ver-1];
		} else if(depx > depy) {
			modify(1, n, rootfa[ver-1], rootfa[ver], y, x);
			rootdep[ver] = rootdep[ver-1];
		} else {
			modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
			modify(1, n, rootdep[ver-1], rootdep[ver], y, depy+1);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	build(1, n, rootfa[0]);
	for (int i=1; i<=m; i++) {
		int opt;
		scanf("%d", &opt);
		if (opt == 1) {
			int a, b;
			scanf("%d%d", &a, &b);
			merge(i, a, b);
		} else if(opt == 2) {
			int k;
			scanf("%d", &k);
			rootfa[i] = rootfa[k];
			rootdep[i] = rootdep[k];
		} else {
			int a, b;
			scanf("%d%d", &a, &b);
			rootfa[i] = rootfa[i-1];
			rootdep[i] = rootdep[i-1];
			int fa = find(i, a);
			int fb = find(i, b);
			printf("%d\n", (fa == fb ? 1 : 0));
		}
	}
	return 0;
}

推荐视频

AgOH–可持久化并查集