介绍
并查集时一种可以动态维护若干个不重叠的集合，并支持合并与查询的数据结构。详细的说，并查集包含以下两个基本操作：
- Get，查询一个元素属于那个集合
- Merge，把两个元素的集合合并为一个大集合
模板代码
const int MAX = 1e5+5;
int f[MAX], n;
//查找，并按节点进行路径压缩
int find(int x){
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
//查找2，按边权压缩
int find(int x) {
if (x == fa[x]) return x;
int root = find(fa[x]);
d[x] += d[fa[x]];
return fa[x] = root; //路径压缩
}
//初始化
void init(){
for(int i=1; i<=n; i++) f[i] = i;
}
例题
| 标题： | 信息学竞赛模板（九）— 并查集 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/69 |
| 更新： | 2022-09-18 22:36:14 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |