并查集是算法竞赛中常用的一种数据结构。
它可以高效地处理集合之间的操作与询问。
其主要功能是查询两个元素是否在同一个集合以及将两个集合合并。
第一部分 并查集的基本操作
算法思想
-
我们将所有元素建成很多棵树（森林），每一棵树就是一个集合。
-
因为并查集是一个树结构，那么每个节点都有一个指针指向父节点。
- 最开始时，每个元素就是一个独立的集合，每个元素各为一棵树且自己就是根及自己指向自己。
- 当我们要查询两个元素是否在同一个集合时，可以判断它们是否在同一棵树上，即只要判断它们所在树的根相同与否就可以了。
比如下图 \(2, 3\) 有相同的根 \(1\)，它们便在一个集合，但是 \(2, 9\) 分别拥有根 \(1, 7\)，不在同一个集合。
- 当我们要合并两个集合时，只要两棵树合并即可，即只要把两棵树的根节点连接起来就可以了。
算法优化（路径压缩）
我们发现，如果建出来的树长这样：
多次查找非常费时间，因为每次都要从最下面跑到最上面。
因为它们都是一个集合的，不在乎它在集合中的顺序，所以我们可以把树变成这样：
即每次查询一个元素在哪一个集合的时候直接把它接在根节点上。
这个可以通过递归实现。
例题
例题1：HDU 1213 How many tables
题目描述
思路
认识的人合并为一个集合，最后查找有多少个集合即可。
查询集合数量有两种方法：
方法1：等所有操作进行完成以后，我们可以查询有多少棵树，也就是查找有多少个根；
方法2：我们定义 \(cnt\) 初始值为 \(n\)，当合并两个不同的集合时，\(cnt\) 就可以 \(-1\)，代表两个集合合并，集合数量少了一个。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int fa[N];
void init() {
for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int u) {
if (u == fa[u]) return u;
return fa[u] = find(fa[u]);
}
void merge(int a, int b) {
int fx = find(a), fy = find(b);
if (fx != fy) fa[fx] = fy;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
int cnt = n;
init();
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
if (find(x) != find(y)) cnt--;
merge(x, y);
}
cout << cnt << '\n';
}
return 0;
}
例题2：P3958 [NOIP2017 提高组] 奶酪
题目描述
思路
如果两个圆的中心相距不超过 \(2R\)，\(R\) 为半径，那么就将两个洞合并为一个集合；
如果一个圆的中心与上下表面相距不超过 \(R\)，那么就将洞与上下表面合并；
最后看看上下表面受否在同一个集合，如果在同一个集合，那么一定可以从下走到上。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
double h, r;
struct pos {
double x, y, z;
} p[N];
int fa[N];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fx] = fy;
}
double dis(int v1, int v2) {
double x = p[v1].x, y = p[v1].y, z = p[v1].z;
double a = p[v2].x, b = p[v2].y, c = p[v2].z;
return sqrt((x - a) * (x - a) + (y - b) * (y - b) + (z - c) * (z - c));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n >> h >> r;
for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y >> p[i].z;
for (int i = 0; i <= n + 1; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (dis(i, j) <= 2 * r) {
merge(i, j);
}
}
}
for (int i = 1; i <= n; i++) {
if (p[i].z <= r) merge(0, i);
if (p[i].z >= h - r) merge(n + 1, i);
}
if (find(0) == find(n + 1)) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
例题3：P1111 修复公路
题目描述
思路
我们将所有公路按照修复时间从小到大排序，然后一个一个合并过去，如果什么时候只有一个联通块时就是最少的时间。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct road {
int x, y, t;
} r[N];
int n, m;
int fa[N];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return 0;
fa[fx] = fy;
return 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) cin >> r[i].x >> r[i].y >> r[i].t;
sort(r + 1, r + m + 1, [](const road a, const road b) { return a.t < b.t; });
int cnt = n;
for (int i = 1; i <= m; i++) {
int x = merge(r[i].x, r[i].y);
cnt -= x;
if (cnt == 1) {
cout << r[i].t << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
第二部分 带权并查集
算法思路
即为树上的每一条边赋上一个权值，比如边的长度，维护该节点与父节点的关系。
相应的，当我们进行路径压缩的优化时，我们发现所有的节点都接到根上边去了，那么这时每一条边也自然而然地变成了维护该节点与根节点的关系。
比如权值是是长度时，我们要根据路径压缩的结果对路径权值进行更新：
路径压缩时更新权值
还是路径长度的例子（如上图），
当我们的父节点 \(f\) 已经被成功合并到根节点时，
我们自然而然地想到如何更新子节点 \(x\) 的距离信息，
看下面的图可以帮助理解
有 \(d[x] = d[x_原] + d[f]\)，
\(d[x_原]\) 表示 \(x\) 节点与原来的父节点的距离，
现在的 \(x\) 的父节点变成了根，我们可以想到上面的公式。
合并时更新权值
假如给定 \(x\) 点和 \(y\) 点的距离为 \(v\)，
然后我们要将 \(x\) 所在集合和 \(y\) 所在集合合并，
如何处理呢？
我们把 \(x\) 树接到 \(y\) 上，
更新父节点的方式还是 \(fa[rx] = ry\)，
我们发现只有一条边发生改变，就是图中标红的边（\(d[rx]\)）：
\(d[rx]\) 被更改了，
其他边都可以随着调用上面讲的 \(find\) 函数进行更新。
怎么更新 \(d[rx]\) 呢，
我们可以利用高中数学知识（向量）去理解，
容易发现 \(d[rx] = -d[x] + v + d[y]\)。
这里举的是路径长度的问题，在遇到各种题目时中可以灵活运用，将 \(+\) 改成 \(\times -\) 等。
例题
例题4：HDU3038 How Many Answers Are Wrong
题目描述
思路
对于一个区间 \([l, r]\) 的和为 \(s\) 我们可以这样理解：\(l - 1\) 和 \(r\) 的差距为 \(s\)。
我们能想到这一点就非常简单了，把刚刚的 \(a, b\) 两点的路径长度改成 \(l - 1\) 和 \(r\) 相差 \(s\) 即可。
直接套用模板。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m;
int fa[N];
int d[N];
int ans;
void init() {
ans = 0;
for (int i = 0; i <= n; i++) fa[i] = i, d[i] = 0;
}
int find(int u) {
if (u == fa[u]) return u;
int f = fa[u];
fa[u] = find(fa[u]);
d[u] += d[f];
return fa[u];
}
void merge(int x, int y, int v) {
int fx = find(x), fy = find(y);
if (fx == fy) {
if (d[y] - d[x] != v) {
ans++;
}
}
else {
fa[fy] = fx;
d[fy] = -d[y] + v + d[x];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n >> m) {
init();
for (int i = 1; i <= m; i++) {
int l, r, s;
cin >> l >> r >> s;
merge(l - 1, r, s);
}
cout << ans << '\n';
}
return 0;
}
例题5：POJ1703 Find them, Catch them
题目描述
题目翻译出来有很多种，有说吃糖的，有说警察抓小偷的。。。
思路
一样的道理，如果一个节点 \(x\) 与父节点的糖的类型相同，那么 \(d[x] = 0\)，如果不同 \(d[x] = 1\)。
对于第一种操作 D a b ，我们只要知道 \(x\) 点和 \(y\) 点的关系为 \(1\) 即可。
对于第二种操作 A a b，我们只要知道 \(x\) 点和 \(y\) 点与根节点的关系是否相同即可。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int d[N];
int fa[N];
void init() {
for (int i = 0; i <= n; i++) fa[i] = i, d[i] = 0;
}
int find(int x) {
if (x == fa[x]) return x;
int f = fa[x];
fa[x] = find(fa[x]);
d[x] += d[f];
return fa[x];
}
void merge(int x, int y, int v) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fx] = fy;
d[fx] = -d[x] + v + d[y];
}
int mod(int x, const int m) {
return (x % m + m) % m;
}
void solve() {
scanf("%d%d", &n, &m);
init();
char opt[2];
int a, b;
for (int i = 1; i <= m; i++) {
scanf("%s%d%d", opt, &a, &b);
if (*opt == 'A') {
int fa = find(a), fb = find(b);
if (fa != fb) printf("Not sure yet.\n");
else if (mod(d[a] - d[b], 2) == 0) printf("In the same gang.\n");
else printf("In different gangs.\n");
}
else {
merge(a, b, 1);
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}
例题6：P1525 [NOIP2010 提高组] 关押罪犯
题目描述
思路
我们将所有的关系看成边，所有的犯人看成点，将边按照怒气值从大到小排序。
利用贪心，我们从前往后枚举，那么越靠前的怒气值越大，我们越不希望将其保留下来，我们更希望将他们放进两个监狱。
于是我们套路化地将那两个犯人连上一条权值为 \(1\) 的边，表示他们最好呆在两个监狱。
当什么时候发生矛盾时，那么那个边的怒气值就是答案，也是省长会看到的值。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20010, M = 100010;
struct edge {
int u, v, w;
} e[M];
bool cmp(const edge a, const edge b) {
return a.w > b.w;
}
int n, m;
int fa[N];
int d[N];
int mod(int x, const int m) {
return (x % m + m) % m;
}
int find(int x) {
if (x == fa[x]) return x;
int f = fa[x];
fa[x] = find(fa[x]);
d[x] = mod(d[x] + d[f], 2);
return fa[x];
}
bool merge(int x, int y, int v) {
int fx = find(x), fy = find(y);
if (fx == fy) {
if (mod(d[x] - d[y], 2) != v) {
return false;
}
}
else {
fa[fx] = fy;
d[fx] = mod(-d[x] + v + d[y], 2);
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; i++) {
if (!merge(e[i].u, e[i].v, 1)) {
cout << e[i].w << '\n';
return 0;
}
}
cout << 0 << '\n';
return 0;
}
例题7：P1196 [NOI2002] 银河英雄传说
题目描述
思路
这次权值维护方法的不太一样。
我们将一列的战舰当作一个集合，
通过并查集维护集合和每一个点 \(u\) 到根节点的距离 \(dis[u]\)，
调查同一个集合的 \(u, v\) 相差多少个战舰可以通过 \(|dis[u] - dis[v]| - 1\) 算出；
合并 \(x\) 到 \(y\) 时，注意修改 \(dis[x]\) 为 \(y\) 树原来的大小，\(y\) 树的大小要加上 \(d[x]\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
int fa[N];
int sz[N];
int d[N];
void init() {
for (int i = 1; i < N; i++) fa[i] = i, sz[i] = 1, d[i] = 0;
}
int find(int x) {
if (x == fa[x]) return x;
int f = fa[x];
fa[x] = find(fa[x]);
d[x] += d[f];
return fa[x];
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fx] = fy;
d[fx] = sz[fy];
sz[fy] += sz[fx];
}
int query(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) return -1;
return max(0, abs(d[x] - d[y]) - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int T;
cin >> T;
char opt;
int x, y;
while (T--) {
cin >> opt >> x >> y;
if (opt == 'M') merge(x, y);
else cout << query(x, y) << '\n';
}
return 0;
}