#创作计划# 并查集
2026-05-05 13:29:39
发布于：广东
Upd 26-05-05:增加了启发式合并的内容和初始化函数。
前言
读了读 Macw 的并查集帖子，感觉大脑被暗杀了。
所以这期讲草履虫都能学会的并查集。
请浅色模式使用。
正文
什么是并查集
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素．[1]
人话：并查集可以管理一些元素和一堆包含这些元素的集合（互不重叠），并查集中这些集合表示为一棵树。因为有很多集合，所以并查集是一个森林。
同时，并查集支持两种操作：
- 合并，即合并两个元素所属集合。
- 查询，即查询一个元素所属的集合（所属树的根节点）。
然而，并查集无法以较低时间复杂度分离集合。
实现并查集
下文中，
parent[i]表示节点 的父节点，n表示并查集中的节点数量。
初始化
初始时，每个元素都属于一个单独的集合（单独的树）。由于此时集合只有一个元素，所以对应的树只有根：
代码上，为了方便查询，将每个根节点的爹父节点设置为自己。
void init(){
for(int i = 1;i <= n;i++) parent[i] = i;
}
查询
我们先把树变成这个样子：
比如我们要查询节点 的根节点，就要这样一步一步往上查找（红色箭头）：
得出答案，节点 是节点 的根节点。
代码实现很简单，根据parent的值向上查询。
int find(int x){//返回节点 x 的根节点编号
if(parent[x] == x) return x;//父节点编号等于自身的节点是根节点
else return find(parent[x]);//不是根节点，向父节点查询
}
路径压缩
在查询时，可以把已经查询过的元素的爹直接设置为根节点，这样元素还是在原来的集合/树中，只是树的高度减少了：
int find(int x){//返回节点 x 的根节点编号
if(parent[x] == x) return x;//父节点编号等于自身的节点是根节点
else{
parent[x] = find(parent[x]);//不是根节点，向父节点查询，同时存储以压缩路径
return parent[x];//返回查询答案
}
}
合并
合并相对简单，让一棵树的根的爹变成另一个树的根即可。
void unite(int x,int y){//合并节点 x,y 所属的集合
parent[find(x)]//x 的根的父节点
=
find(y);//y 的根
}
启发式合并
两棵树的合并顺序并不影响并查集的正确运行，但是会影响并查集的运行效率。
一般来说，我们可以选择节点数量少/深度小的树合并到另一棵，来防止退化。
为什么会退化？考虑一个极端情况（一棵深度为 1 而另一棵深度为 10），如果把深度大的接到深度小的就会得到一颗深度11的树，而反之深度只为10。由此可以想到对于任意深度的树此操作都会防止退化。
具体复杂度见：https://oi-wiki.org/ds/dsu/#%启发式合并 "具体复杂度讨论"
这里给出一个按节点数量合并的方法，注意要调整初始化：
int n,parent[200010],cnt[200010];//cnt为节点数量
void init(){
for(int i = 1;i <= n;i++) parent[i] = i,cnt[i]=1;//初始化节点数量
}
//省略查询......
void unite(int x,int y){
x=find(x),y=find(y);
if(cnt[x]<cnt[y]) swap(x,y);//交换，令x的节点数量大于y的节点数量
pa[y] = x;//节点数量少的爹变另一个
cnt[x] += cnt[y];//合并节点数量
}
最终代码
此代码没有启发式合并，只有路径压缩。
int n,parent[200010];
void init(){
for(int i = 1;i <= n;i++) parent[i] = i;
}
int find(int x){//返回节点 x 的根节点编号
if(parent[x] == x) return x;//父节点编号等于自身的节点是根节点
else{
parent[x] = find(parent[x]);//不是根节点，向父节点查询，同时存储以压缩路径
return parent[x];//返回查询答案
}
}
void unite(int x,int y){//合并节点 x,y 所属的集合
parent[find(x)]//x 的根的父节点
=
find(y);//y 的根
}
例题
P3367 【模板】并查集 / A47207.【模板】并查集
标准并查集，注意不做路径压缩会炸一半。
#include<bits/stdc++.h>
using namespace std;
int n,parent[200010];
int find(int x){//返回节点 x 的根节点编号
if(parent[x] == x) return x;//父节点编号等于自身的节点是根节点
else{
parent[x] = find(parent[x]);//不是根节点，向父节点查询，同时存储以压缩路径
return parent[x];//返回查询答案
}
}
void unite(int x,int y){//合并节点 x,y 所属的集合
parent[find(x)]//x 的根的父节点
=
find(y);//y 的根
}
int m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
parent[i] = i;//初始化
}
for(int i = 1;i <= m;i++){
int z,x,y;cin >> z >> x >> y;
if(z == 1){
unite(x,y);//合并
}
if(z == 2){
if(find(x) == find(y)) cout << "Y\n";//是一个爹
else cout << "N\n";//不是一个爹
}
}
}
参考
https://www.acgo.cn/discuss/study/18046
有帮助，赞一个