1359 字
7 分钟
并查集
1. 引言部分
-
痛点分析：
- 若无，则难以判断元素是否在同一集合下
-
价值阐述：
- 能够元素是否在同一集合中，记录集合大小等数据，若是有属性联系，还可以加上带权并查集，得到点与点的联系(比如 A 与 B点的奇偶性，A吃B等等)
- 将几个零散的点合并成一个点，简化问题
-
应用场景：
- 三元关系中说谎话
A->B, B->C, C->A - A B之间奇偶关系
- 三元关系中说谎话
引言
在算法竞赛和工程开发中，我们经常遇到这样的问题，题目给出A，B，C，D，让我们去维护它们之间的关系
传统的暴力解法需要O(n²)的时间，在数据量大时完全不可行。
这时候用并查集的思想，将所有相同类型的数据合并即可（这里的思想有点像缩点 缩边） 只用处理祖先元素即可
2. 基本概念解释
什么是并查集？
想象一下，有一个衣架，下面挂着很多很多衣服，同时挂在同一个衣架上有一个特性，都是一个人穿的衣服，这样就是我们并查集模型，我们能直接通过拿去衣架，知道，该衣架下的属性（衣服个数，属于谁等等)
定义
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。
3. 核心操作详解
每个操作包含：
-
算法步骤
- 这里假定 A 和 B 两者链接:
- 首先得得到 A 和 B的祖先 PA 和 PB
- 再更新 PA 和 PB 之间的关系
（通过find路径压缩也会同时更新在原先祖先节点为PA的所有点) - 最后将 PA的祖先指向 PB 即形成链接
-
复杂度分析
- 有路径压缩的原因：查找基本上在
O(1)左右 - 空间复杂度在
O(n)
- 有路径压缩的原因：查找基本上在
-
示例说明
- 问 A 和 B 是否在同一集合，只用查询 两个人的祖先是否同一个
- 即：
find(a) == find(b) ? 1 : 0;
4. 完整代码实现
- 本题以食物链为原型，详细题解查看食物链
#include <iostream>#include <algorithm>
using namespace std;
const int N = 5e4 + 10;
int n, m;//p代表 并查集， d代表该子节点 与 根节点的距离//根据题目意思 A B C 三者必定存在回想制约的关系//所以 可以设 距离 余0 是相同 余 1 是吃根 余而 2是 被根吃int p[N], d[N];
//查找的同时 并更新状态int find(int x){ if(x != p[x]) { int t = find(p[x]); //因为 根节点发生转变， 先添加此时父亲节点 的值 再连接到根节点 d[x] += d[p[x]]; //再将 x 的父节点 转变为 新查找到的 父节点 p[x] = t; } return p[x];}
int main(){ scanf("%d%d", &n , &m);
for(int i = 1; i <= n; i++) p[i] = i;
int res = 0; while(m --) { int t ,x, y; scanf("%d%d%d", &t, &x, &y);
int px = find(x), py = find(y); //将两个 根节点查找 if(x > n || y > n) res++; else { if(t == 1) { //如果相等 则 判断 是否 不等 if(px == py && (d[x] - d[y]) % 3) res++; //如果不等 else if(px != py) { //将 x 的根 连接到 p 的根 p[px] = p[y]; // 加入某个值 使得 整体效果不变//又因为 x 和 y 同族 所以 d[x] + ? = d[y] (mod 3); d[px] = d[y] - d[x]; } } else { if(px == py && (d[x] - d[y] - 1) % 3) res ++; else if(px != py) { p[px] = p[y]; //余 1 吃//同理 此时 d[x] - 1 + ? = d[y] (mod 3) d[px] = d[y] + 1 - d[x]; } } }
} printf("%d\n",res); return 0;}5. 例题解析
选择梯度式例题：
-
基础题：
-
进阶题：食物链，奇偶游戏
6. 复杂度分析表
| 操作 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 初始祖先 | O(n) | O(n) | 初始祖先指向自己 |
| 单点更新 | O(1) | - | 递归深度 |
7. 实战技巧
- 常见错误及调试方法
- 对于带权并查集中的
find函数使用需注意:优先更新祖先的节点，再将跟新完后的节点反馈给自己,比如
//查找的同时 并更新状态 - 对于带权并查集中的
int find(int x)
{
if(x != p[x])
{
int t = find(p[x]);
//因为 根节点发生转变， 先添加此时父亲节点 的值 再连接到根节点
d[x] += d[p[x]];
//再将 x 的父节点 转变为 新查找到的 父节点
p[x] = t;
}
return p[x];
}
```
- 同时还需要注意：不能对祖先赋值完后，在没更新祖先的新祖先前，重复使用find函数，会导致d[x] 不断累加 例如：
if(s=='M'){ if(find(a)!=find(b)){ d[find(a)]=sum[find(b)]; sum[find(b)]+=sum[find(a)]; //每次find 都会累加 p[find(a)]=find(b); } }-
还有方向性，
p[pa] = pb是让 pb成为pa新的祖先,若题目有要求则需要额外判定，如没有则无需 -
模板代码整理
//带权int find(int x){ if(x != p[x]) { int t = find(p[x]); //因为 根节点发生转变， 先添加此时父亲节点 的值 再连接到根节点 d[x] += d[p[x]]; //再将 x 的父节点 转变为 新查找到的 父节点 p[x] = t; } return p[x];}//不带权int find(x){ if(x != p[x]) p[x] = find(p[x]); return p[x];}部分信息可能已经过时