并查集是算法竞赛中常用的一种数据结构。
它可以高效地处理集合之间的操作与询问。
其主要功能是查询两个元素是否在同一个集合以及将两个集合合并。
第一部分 并查集的基本操作
算法思想
-
我们将所有元素建成很多棵树（森林），每一棵树就是一个集合。
-
因为并查集是一个树结构，那么每个节点都有一个指针指向父节点。
- 最开始时，每个元素就是一个独立的集合，每个元素各为一棵树且自己就是根及自己指向自己。
- 当我们要查询两个元素是否在同一个集合时，可以判断它们是否在同一棵树上，即只要判断它们所在树的根相同与否就可以了。
比如下图 (2, 3) 有相同的根 (1)，它们便在一个集合，但是 (2, 9) 分别拥有根 (1, 7)，不在同一个集合。
- 当我们要合并两个集合时，只要两棵树合并即可，即只要把两棵树的根节点连接起来就可以了。
算法优化（路径压缩）
我们发现，如果建出来的树长这样：
多次查找非常费时间，因为每次都可能要从最下面跑到最上面。
因为它们都是一个集合的，不在乎它在集合中的顺序或位置，所以我们可以把树变成这样：
即每次查询一个元素在哪一个集合的时候顺便把它接在根节点上。
下面我们通过例题讲讲如何实现该数据结构。
例题
例题1：P3367 【模板】并查集
题目描述
思路
模板题，将上面讲述的思路应用到代码中即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
int fa[N];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]); // 将根节点直接作为 x 点的父亲节点
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fx] = fy; // 将两个根节点合并
}
void init() {
for (int i = 1; i <= n; i++) fa[i] = i;// 初始化
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
if (x == 1) merge(y, z);
else {
if (find(y) == find(z)) cout << "Yn";
else cout << "Nn";
}
}
return 0;
}
例题2：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--; // 方法2统计结果
merge(x, y);
}
cout << cnt << 'n';
}
return 0;
}
例题3：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 << "Yesn";
else cout << "Non";
}
return 0;
}
例题4：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) 所在集合合并，就可以实现调查任意两点的关系（距离）
如何处理呢？
我们把 (x) 树接到 (y) 上，
还是直接将 (x) 所在子树的根接到 (y) 所在的子树的根即可。
我们现在开始处理 (d) 数组。
我们发现只要更改一条边，就是图中标红的边（(d[rx])）就够了：
因为 (d[rx]) 被更改了，
其他边都可以随着调用上面讲的 (find) 函数进行更新。
怎么更新 (d[rx]) 呢，
我们可以利用高中数学知识（向量）去理解，
容易发现 (d[rx] = -d[x] + v + d[y])。
这里举的是路径长度的问题，在遇到各种题目时中可以灵活运用，比如将 (+) 改成 (times - xor) 等。
例题
例题5：POJ1703 Find them, Catch them
题目描述
题目翻译出来有很多种，有说吃糖的，有说警察抓小偷的。。。
思路
一样的道理，如果一个节点 (x) 与父节点的糖的类型相同，那么关系 (d[x] = 0)，如果不同 (d[x] = 1)。
显然在 (find) 函数中 (d[x]) 可以这么更新： (d[x] = (d[x] + d[f]) mod 2)。
对于第一种操作 D a b ，我们就可以知道 (a) 点和 (b) 点的关系为 (1)。
对于第二种操作 A a b，
首先，如果 (a) 和 (b) 在不同的集合，我们不能知道它们之间的关系，
否则，(a) 和 (b) 在相同的集合，我们只要知道 (a) 点和 (b) 点与根节点的关系是否相同即可，即 (d[a] - d[b]) 如果等于 (0)，那么 (a) 和 (b) 类型相同，否则不同。
代码
#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：HDU3038 How Many Answers Are Wrong
题目描述
思路
对于一个区间 ([l, r]) 的和为 (s) 我们可以这样理解：(l - 1) 和 (r) 的差距为 (s)。
我们能想到这一点就非常简单了，把刚刚的 (a, b) 两点的路径长度改成 (l - 1) 和 (r) 相差 (s) 即可。
显然在 (find) 函数中 (d[x]) 可以这么更新： (d[x] = d[x] + d[f])。
直接套用模板。
代码
#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]; // 保存当前父节点 f，一会要通过 d[f] 更新 d[u]
fa[u] = find(fa[u]); // 路径压缩
d[u] += d[f]; // 通过 d[f] 更新 d[u]
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); // 注意 l 要 -1
}
cout << ans << 'n';
}
return 0;
}
例题7：P1525 [NOIP2010 提高组] 关押罪犯
题目描述
思路
我们将所有的关系看成边，所有的犯人看成点，将边按照怒气值从大到小排序。
利用贪心，我们从前往后枚举，那么越靠前的怒气值越大，我们越不希望将其保留下来，我们更希望将他们放进两个监狱。
于是我们套路化地将那两个犯人连上一条权值为 (1) 的边，表示他们最好呆在两个监狱。
显然在 (find) 函数中 (d[x]) 可以这么更新： (d[x] = (d[x] + d[f]) mod 2)。
即“敌人的敌人是朋友”。
当什么时候发生矛盾时（比如两个积怨很深的人不得不在一起时），那么那个边的怒气值就是答案。
代码
#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;
}
例题8：P1196 [NOI2002] 银河英雄传说
题目描述
思路
这次权值维护方法的不太一样。
我们将一列的战舰当作一个集合，
通过并查集维护集合和每一个点 (u) 到根节点的距离 (dis[u])，
调查同一个集合的 (u, v) 相差多少个战舰可以通过 (|dis[u] - dis[v]| - 1) 算出；
合并 (x) 到 (y) 时，注意修改 (dis[x]) 为 (y) 树原来的大小 (sz[y])，然后 (y) 树的大小 (sz[y]) 要加上 (sz[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;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
