并查集是算法竞赛中常用的一种数据结构。
其主要功能是查询两个元素是否在同一个集合以及将两个集合合并。
第一部分 并查集的基本操作
算法思想
- 我们将所有元素建成很多树(森林),每一棵树就是一个集合,比如下图有 \(\{1, 2, 3, 4, 5, 6\}, \{7, 9, 10, 11, 12, 13\}\) 两个集合。
- 我们将每一棵树的根当作判断依据,当我们要查询两个元素是否在同一个集合时,可以判断它们是否在同一棵树上,即只要判断它们所在树的根相同与否就可以了,比如下图 \(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;
}
第二部分 带权并查集
即为树上的每一条边赋上一个权值,比如边的长度。
相应的,当我们进行路径压缩的优化时,也要不断地更新权值。
比如权值是变得长度时,我们要根据路径压缩的结果对路径权值进行更新: