当前位置：首页 > news >正文

【数据结构】并查集：从入门到精通

news 2025/8/13 7:16:28

并查集的基本概念

并查集是一种树形的数据结构，主要支持**合并（Union）和查找（Find）**两种操作：

合并：将两个不相交的子集合合并成一个统一的集合（合并相应的根节点）。
查找：查询元素所属的集合（找根节点）。

父节点数组 fa[]

作用：fa[x] 存储节点 x 的父节点。
初始化：每个节点初始时是独立集合，指向自身。

for (int i = 1; i <= n; i++)fa[i] = i

例如，初始状态下 fa[1] = 1、fa[2] = 2 等，每个节点自成一个集合。

查找操作（Find）

基本查找

查找的目标是找到元素所在集合的根节点，过程如下：

int Find(int x) {if (fa[x] == x) return x;  // 父节点是自身，找到根return Find(fa[x]);        // 递归查找父节点的根
}

路径压缩优化

为了加速后续查找，可在查找时压缩路径，让路径上的节点直接指向根：

int Find(int x) {if (fa[x] == x) return x;  return fa[x] = Find(fa[x]);  // 递归查找并直接指向根
}

合并操作（Union）

基本合并

将两个集合合并，做法是把一个集合的根指向另一个集合的根：

void Union(int x, int y) {fa[Find(x)] = Find(y);  // x 所在集合的根指向 y 所在集合的根
}

按秩合并

为避免合并后树过高影响效率，可按集合大小（或深度）合并，把小集合的根指向大集合的根。

按高度合并

1. 核心思想

合并时，让较矮树的根指向较高树的根；
若两棵树高度相同，合并后新树高度会 +1 。
这样能保证树的高度尽可能小，让 find 操作（查找根）更快。

2. 关键变量

h[] 数组：h[root] 存储以 root 为根的树的高度。
fa[] 数组：存储节点的父节点。

3. 代码展示

void Union(int x, int y){int rootx = Find(x);  // 找到 x 所在集合的根int rooty = Find(y);  // 找到 y 所在集合的根if(rootx != rooty)   // 不在同一集合才合并{   if(h[rootx] < h[rooty]) //x 所在树更矮 → 让 x 的根指向 y 的根 fa[rootx] = rooty;  else if(h[rootx] > h[rooty])// y 所在树更矮 → 让 y 的根指向 x 的根fa[rooty] = rootx;  else// 两棵树高度相同 → 随便选一个{fa[rootx] = rooty;  h[rooty]++;  // 合并后，新树高度 +1 }}
}

合并后树的高度被严格控制，find 操作的时间会更稳定，接近 $O (α (n))$ （阿克曼函数反函数，极高效）。

按节点数量合并

1. 核心思想

合并时，让较小集合的根指向较大集合的根。这样能保证大集合的树尽可能“粗壮”，小集合合并进来不显著增加树的高度，间接让 find 更快。

2. 关键变量

s[] 数组：s[root] 存储以 root 为根的集合的节点总数（初始时每个节点自身为集合，s[i]=1 ）。
fa[] 数组：存储节点父节点。

3. 代码展示

void Union(int x, int y){int rootx = Find(x);  // 找 x 的根int rooty = Find(y);  // 找 y 的根if(rootx != rooty)// 不同集合才合并{   if(s[rootx] <= s[rooty])// x 集合更小（或相等）→ 让 x 的根指向 y 的根{  p[rootx] = rooty;  s[rooty] += s[rootx];  // y 集合大小 += x 集合大小 }else// y 集合更小 → 让 y 的根指向 x 的根{p[rooty] = rootx;  s[rootx] += s[rooty];  // x 集合大小 += y 集合大小 }}
}

总结对比

对比项	按高度合并	按节点数量合并
核心优化点	控制树的高度，避免合并后树过高	控制集合大小，让小集合合并进大集合
关键数组	`h[]` 存树高，`fa[]` 存父节点	`s[]` 存集合大小，`fa[]` 存父节点
适用场景	对“树高度敏感”，或需严格限制树高	需频繁查“集合大小”，或追求“通用高效”
实际效率	接近 $O (α (n))$ ，树高控制更直接	接近 $O (α (n))$ ，额外支持“集合大小查询”

例题训练

来一个模板题练练手：

P3367 【模板】并查集

题目来源

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=2e5+6;
int n,m,f[N],z,x,y,h[N];
int Find(int x)
{if(f[x]==x)return x;else return Find(f[x]);
}
void Union(int x,int y)
{int rx=Find(x);int ry=Find(y);if(rx!=ry){if(h[rx]<h[ry])f[rx]=ry;else if(h[rx]>h[ry])f[ry]=rx;else{f[rx]=ry;h[ry]++;}}
} 
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i,h[i]=1;while(m--){cin>>z>>x>>y;if(z==1)Union(x,y);else if(z==2){int tx=Find(x);int ty=Find(y);if(tx==ty)cout<<"Y"<<endl;elsecout<<"N"<<endl;}}
}
signed main()
{IOS;int _=1;
//	cin>>_;while(_--)solve();return 0;
}