带权并查集

并查集在维护不相交集类关系时, 可以同时维护同一集合元素之间的某些特殊联系, 例如大小、长度等, 这种并查集称之为带权并查集. 任何可通过并查集中父子关系快速递推的量, 即:

可以快速得到计算的量$w$, 都可以作为权使用并查集维护.

基于上式, 在路径压缩时权可以一并压缩, 从而保证并查集的$O(\alpha (N))$复杂度不变.

路径压缩写法

是一种套路:

int find(int x)
{
	if (fa[x] == x)
		return x;
	int rt = find(fa[x]);
	w[x] = op(w[x], w[fa[x]]);//!!!
	return fa[x] = rt;
}
​

例题1. 洛谷P1196 [NOI2002] 银河英雄传说

题意

大概是一字长蛇阵, 一开始每人一列, 然后支持合并两列(首尾相连)和查询在同一列中的两人距离.

分析

需要合并, 自然想到使用并查集. 距离能否快速维护呢? 只要时刻在每个集合根节点处维护该队列长度$len$即可. 新合并进来的节点距根节点距离$dis$就等于$len$, 然后再更新$len$即可.

代码

#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define FOR(x, y, z) for (int x = y; x <= z; x++)
typedef long long ll;
typedef pair<int, int> pii;
#define N 30004
int t;
int fa[N], dis[N], len[N]; // dis指的是到根节点的距离
void init()
{
	FOR(i, 1, 30000)
	{
		fa[i] = i;
		dis[i] = 0;
		len[i] = 1;
	}
}
int find(int x)
{
	if (fa[x] == x)
		return x;
	int rt = find(fa[x]);
	dis[x] += dis[fa[x]];
	return fa[x] = rt;
}
void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	fa[fx] = fy;
	dis[fx] = len[fy];
	len[fy] += len[fx];
}
int main()
{
	init();
	cin >> t;
	while (t--)
	{
		char op;
		int i, j;
		scanf(" %c", &op);
		cin >> i >> j;
		if (op == 'M')
			merge(i, j);
		else
		{
			if (find(i) == find(j))
				cout << abs(dis[i] - dis[j]) - 1 << endl;
			else
				cout << -1 << endl;
		}
	}
	return 0;
}
​

种类并查集

普通的并查集, 同一集合一般用来维护同种元素, 种类并查集是使用带权并查集维护同一集合元素间不同关系的一种特殊带权并查集. 在这里, 权代表的是父子之间的种类关系(同类、对立、上下游等).

同普通带权并查集一样, 只要这种关系满足

可快速递推, 就可以作为种类使用带权并查集维护.

例题2. 洛谷P2024 [NOI2001] 食物链

题意

现有ABC三个种类, 形成一个循环的食物链. 给定$n$种动物, 各属于其中一类. 每次给定下列一个关系:

1. $x$和$y$同属一类
2. $x$吃$y$

请给出有多少不合法关系. 冲突时, 以较早出现的关系为准, 晚出现的关系为不合法关系.

分析

以往习惯用反集来处理这种集合间的关系, $\overline{A}$表示与$A$具有某种关系的集合, 然后藉由$\overline{A}$来合并对$A$具有同样关系的元素所在集合.

但有了带权并查集之后, "权"可以很自然的用来维护父子关系, 这样集合就不再是等价可传递关系, 而是维护的一种普通可演算(传递时需要进行一定演算)的关系.

只要关系可以演算后传递, 那么就能用并查集来维护. 只要在$find$带压缩时计算一下当前点合并后的关系即可.

代码

#include <bits/stdc++.h>
using namespace std;
#define FOR(x, y, z) for (int x = y; x <= z; x++)
int n, k;
#define N 50004
int fa[N], rel[N]; // rel代表x和fa[x]的关系 0:同类, 1:子吃父, 2:父吃子
void init()
{
	FOR(i, 1, n)
	fa[i] = i, rel[i] = 0;
}
int find(int x)
{
	if (fa[x] == x)
		return x;
	int root = find(fa[x]);
	rel[x] = (rel[x] + rel[fa[x]]) % 3; //同类、吃、被吃关系的转换
	//注意这里要用fa[x], 不能直接跳到root
	return fa[x] = root;
}
int main()
{
	cin >> n >> k;
	init();
	int ans = 0;
	while (k--)
	{
		int o, x, y;
		cin >> o >> x >> y;
		if (x > n || y > n || o == 2 && x == y)
		{
			ans++;
			continue;
		}
		auto fx = find(x), fy = find(y); // find完成之后路径已经压缩, 所以可以直接使用fx和fy的rel
		if (o == 1)
		{
			if (fx != fy)
			{
				fa[fx] = fy;
				rel[fx] = (3 - rel[x] + rel[y]) % 3; // rel[x-->fx]和rel[y-->fy]都要考虑进去
			}
			else if (rel[x] != rel[y])
				ans++;
		}
		else
		{
			if (fx != fy)
			{
				fa[fx] = fy;
				rel[fx] = (4 - rel[x] + rel[y]) % 3;// 这些关系的演算法则可以推一下真值表
			}
			else if ((rel[x] - rel[y] + 3) % 3 != 1)
				ans++;
		}
	}
	cout << ans;
	return 0;
}
​

一些较为重要的细节, 都已经写在注释里面了.