并查集

AisDaeun 10 2023-10-29

1、基础并查集

直接上例题:

尽量少砸锁 SYOJ P1690
有 N 个房间全部锁着门,每个房间只有一把钥匙。而所有的钥匙也都被锁在房间里了,有的房间钥匙可能被锁在了别的房间里。现在要把所有的房间全打开。如果没有钥匙,只能砸锁。
问:最少需要砸多少个门锁?

如果a房间中有b房间的钥匙,那么只要砸开a房间的门锁,b房间的门锁自然能打开。因此,可以把a、b合并。最后的连通块的个数即为答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int fa[N];
int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) fa[i] = i;
	int ans = n;
	for (int i = 1; i <= n; i++) {
		int j;
		scanf("%d", &j);
		int x = get(i), y = get(j);
		if (x != y) fa[x] = y, ans--;
	}
	printf("%d\n", ans);
	return 0;
}

2、并查集扩展域

把一个点拆成多个点,这种方式的好处是比较简单,但是占用空间比较大。
例如:SYOJ 1688

[BOI2003] 团伙 洛谷P1892
有多对友好关系和敌对关系,求出最多团体数。

那么对每个点建一个反点,设x_i的反点为x_i^{\prime},如果是友好关系则合并(x_i, x_j),如果是敌对关系则分别把x_i^{\prime}合并为x_j的子树,把x_j^{\prime}合并为x_i的子树。统计时,遍历所有的正点,统计所有根节点的个数。

这里有几个点要注意:

  1. 合并敌对关系时不能把x_i合并到x_j^{\prime}。这是因为最后统计的是正点的个数,所以要把反点合并为正点的子树,而不能把正点合并到反点上。

  2. 由于题目没有说朋友的敌人和朋友的敌人是什么关系,因此不能合并x_i^{\prime}, x_j^{\prime}

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int fa[N];
int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
	x = get(x), y = get(y);
	fa[x] = y;
}
int n, m;
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= 2 * n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
		char c; int p, q;
		scanf("%s%d%d", &c, &p, &q);
		if (c == 'F') merge(p, q);
		else merge(p + n, q), merge(q + n, p);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) if (i == fa[i]) ans++;
	printf("%d\n", ans);
}

3、并查集边带权

SYOJ P1692
原题POJ 1984 Navigation Nightmare

#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10, K = 1e4 + 10;
struct node {
	int x, y;
	void operator += (node &a) {x += a.x, y += a.y; }
	int to(node &b) {return abs(x - b.x) + abs(y - b.y); }
} d[N];
int fa[N];
int get(int x) {
	if (x == fa[x]) return x;
	int root = get(fa[x]);
	d[x] += d[fa[x]];
	return fa[x] = root;
}
const int dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
struct edge {
	int u, v, w, dir;
	void fix() {
		int x = get(u), y = get(v);
		fa[y] = x;
		d[y].x = d[u].x - d[v].x + dx[dir] * w;
		d[y].y = d[u].y - d[v].y + dy[dir] * w;
	}
} e[N];
struct query {
	int u, v, t, id;
	bool operator < (query &a) {return t < a.t; }
} q[K];
int ans[N];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) 
		scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].w, &e[i].dir);
	int k;
	scanf("%d", &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d%d%d", &q[i].u, &q[i].v, &q[i].t);
		q[i].id = i;
	}
	sort(q + 1, q + k + 1);
	int j = 1;
	for (int i = 1; i <= m; i++) {
		e[i].fix();
		while (q[j].t <= i && j <= k) {
			int &u = q[j].u, &v = q[j].v, &id = q[j].id;
			int x = get(u), y = get(v);
			if (x != y) ans[id] = -1;
			else ans[id] = d[u].to(d[v]);
			j++;
		}
	}
	for (int i = 1; i <= k; i++) printf("%d\n", ans[i]);
	return 0;
}