C++ 数据结构进阶:并查集原理、实现与面试实战
介绍并查集(Union-Find Set)数据结构,用于处理不相交集合的合并与查询。核心操作包括查找(Find)、合并(Union)和统计集合个数(Count)。通过路径压缩和按大小合并优化,时间复杂度接近常数。文章详细讲解父指针数组原理,提供带路径压缩的 C++ 实现代码,结合 LeetCode 省份数量(547)和等式方程可满足性(990)展示应用。最后分析复杂度及常见误区,帮助掌握动态连通性问题解决方案。

介绍并查集(Union-Find Set)数据结构,用于处理不相交集合的合并与查询。核心操作包括查找(Find)、合并(Union)和统计集合个数(Count)。通过路径压缩和按大小合并优化,时间复杂度接近常数。文章详细讲解父指针数组原理,提供带路径压缩的 C++ 实现代码,结合 LeetCode 省份数量(547)和等式方程可满足性(990)展示应用。最后分析复杂度及常见误区,帮助掌握动态连通性问题解决方案。

在编程世界里,有一类问题始终困扰着初学者 —— 如何高效处理元素的分组、合并与查询?比如判断社交网络中的'朋友圈'数量、验证等式方程的可满足性、解决图的连通分量问题等。如果用常规的暴力方法,不仅代码繁琐,效率也会大打折扣。而并查集(Union-Find Set),这个看似简单却极具智慧的数据结构,正是为解决这类问题而生。
它就像一个'社交圈子管理器',能轻松实现'查找某人属于哪个圈子'和'将两个圈子合并'这两个核心操作,且经过优化后,这两个操作的时间复杂度几乎能达到常数级别。本文将从原理入手,带你层层揭开并查集的神秘面纱,让你从'入门'到'精通',再到'实战应用',真正掌握这个面试与工作中的'利器'。
并查集,也叫 disjoint-set(不相交集合),是一种支持快速查找和合并操作的抽象数据类型,主要用于处理一系列不相交集合的合并与查询问题。
它的核心思想可以用生活中的'朋友圈'来理解:
初始时,每个人都是一个独立的'小圈子'(单元素集合);当两个人成为朋友时,他们所在的'小圈子'就会合并成一个'大圈子'(集合合并);当我们想知道两个人是否是朋友时,只需判断他们是否在同一个'圈子'里(集合查询)。
再举一个更具体的例子:
某公司校招了 10 名新员工,编号 0-9,来自不同城市,起初互不相识(每个员工自成一个集合)。
后来西安的 4 名员工(0、6、7、8)组成小分队,成都的 3 名员工(1、4、9)组成小分队,武汉的 3 名员工(2、3、5)组成小分队(三次集合合并)。
之后,西安的 8 号员工和成都的 1 号员工成为好友,两个小分队又合并成一个大圈子(第四次合并)。我们需要快速回答:'3 号和 7 号是否在同一个圈子?''现在总共有多少个圈子?'
—— 这些问题,并用查集都能高效解决。
简单来说,并查集就是管理'圈子'的数据结构,核心支持三个操作:查找(Find)、合并(Union)、统计集合个数(Count)。
并查集的实现非常巧妙,通常用一个数组就能模拟所有集合的关系。这个数组我们称之为**'父指针数组',记为ufs**(Union-Find Set 的缩写),数组的下标对应元素的编号,数组的值则有特殊含义:
若**
ufs[index] < 0:表示index是一个集合的根节点('圈子的首领'),其绝对值|ufs[index]|表示该集合的元素个数**;若**ufs[index] >= 0:表示index不是根节点,其值指向该元素的'父节点'**(同一个圈子里的上一级成员)。
我们用之前的员工例子来直观理解:
每个员工都是自己的'首领',集合大小为 1,所以数组所有元素都为 -1:
ufs[0] = -4,ufs[6] = 0,ufs[7] = 0,ufs[8] = 0;ufs[1] = -3,ufs[4] = 1,ufs[9] = 1;ufs[2] = -3,ufs[3] = 2,ufs[5] = 2。此时数组状态:
索引:0 1 2 3 4 5 6 7 8 9
ufs:-4 -3 -3 2 1 2 0 0 0 1
8 号(属于 0 的集合)和 1 号(属于 1 的集合)合并,将两个集合合并为一个。此时 0 成为新的根,集合大小为 4+3=7,所以 ufs[0] = -7,ufs[1] = 0(1 的父节点变为 0)。
最终数组状态:
索引:0 1 2 3 4 5 6 7 8 9
ufs:-7 0 -3 2 1 2 0 0 0 1
通过这个数组,我们能快速获取以下信息:
查找元素 6 的根:
ufs[6] = 0(非负),继续查ufs[0] = -7(负),所以根是 0,属于大小为 7 的集合;判断元素 3 和 7 是否同属一个集合:3 的根是 2,7 的根是 0,根不同,所以不属于同一个集合;统计集合个数:数组中负数的个数(0 和 2 对应的 -7、-3),共 2 个集合。
并查集的核心是三个操作:查找(Find)、合并(Union)、统计集合个数(Count),其原理如下:
查找操作的目标是,给定一个元素编号,沿着父指针一直向上追溯,直到找到根节点(数组值为负数的元素)。
步骤:
若当前元素的**
ufs值为负数**,直接返回该元素(根节点);若为非负数,将当前元素更新为其父节点,重复步骤 1,直到找到根节点。
例如,查找元素 9 的根:
ufs[9] = 1(非负)→ 父节点是 1;ufs[1] = 0(非负)→ 父节点是 0;ufs[0] = -7(负)→ 根节点是 0,返回 0。
合并操作的目标是,将两个不同集合的根节点连接起来,形成一个新的集合。
步骤:
分别找到两个元素的根节点**
root1和root2;若root1 == root2:两个元素已在同一个集合,合并失败,返回false;若root1 != root2:将较小的集合合并到较大的集合(优化策略,避免树过深),更新根节点的集合大小(ufs[root1] += ufs[root2]),并将较小集合的根节点的父指针指向较大集合的根节点(ufs[root2] = root1**),合并成功,返回true。
为什么要'小集合合并到大集合'?这是为了避免树的高度过高,导致后续查找操作变慢。比如,如果总是把大连合合并到小集合,可能会形成一条长长的链(如 1→2→3→...→n),查找根节点需要 O(n) 时间;而'小合并到大'能保证树的高度始终较低,查找效率更高。
由于根节点的**ufs**值为负数,非根节点为非负数,所以只需遍历整个数组,统计负数的个数即可。
例如,初始状态数组有 10 个负数,集合个数为 10;合并为三个小分队后,数组有 3 个负数,集合个数为 3;合并西安和成都小分队后,数组有 2 个负数,集合个数为 2。
在上述基础实现中,查找操作的效率取决于树的高度。如果树的高度过高(如链式结构),查找操作的时间复杂度会退化到 O(n)。为了进一步优化查找效率,我们可以引入**'路径压缩'**技术。
路径压缩是指,在执行查找操作时,将查找路径上的所有元素的父指针直接指向根节点。这样一来,下次再查找这些元素时,就能直接找到根节点,大大减少查找次数。
举个例子:原来的查找路径是 9→1→0(根节点),执行路径压缩后,9 的父指针直接指向 0,下次查找 9 时,一步就能找到根节点。
路径压缩的实现非常简单,只需在Find操作中,将当前元素的父节点更新为根节点即可(可以用递归或迭代实现)。优化后的Find操作,时间复杂度几乎能达到O(1)(均摊时间复杂度)。
基于上述原理,我们用 C++ 实现一个通用的并查集类,包含查找(带路径压缩)、合并(小集合合并到大集合)、统计集合个数三个核心操作。
#include <vector>
#include <iostream>
using namespace std;
// 并查集类
class UnionFindSet {
public:
// 构造函数:初始化并查集,每个元素自成一个集合(值为 -1)
UnionFindSet(size_t size) : _ufs(size, -1) {}
// 查找操作:找到元素 index 的根节点,带路径压缩
int FindRoot(int index) {
// 边界检查:index 必须在合法范围内
if (index < 0 || index >= _ufs.size()) {
throw invalid_argument("index out of range");
}
// 迭代实现路径压缩:找到根节点后,回溯更新路径上所有元素的父节点
int root = index;
// 第一步:找到根节点
while (_ufs[root] >= 0) {
root = _ufs[root];
}
// 第二步:路径压缩,将 index 到 root 路径上的所有元素直接指向 root
while (_ufs[index] >= 0) {
int parent = _ufs[index];
_ufs[index] = root;
index = parent;
}
return root;
}
// 合并操作:将 x1 和 x2 所在的集合合并,返回是否合并成功
bool Union(int x1, int x2) {
// 找到两个元素的根节点
int root1 = FindRoot(x1);
root2 = (x2);
(root1 == root2) {
;
}
(_ufs[root1] > _ufs[root2]) {
(root1, root2);
}
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
;
}
{
count = ;
( e : _ufs) {
(e < ) {
++count;
}
}
count;
}
{
cout << ;
( e : _ufs) {
cout << e << ;
}
cout << endl;
}
:
vector<> _ufs;
};
{
;
cout << << endl;
ufs.();
cout << << ufs.() << endl;
ufs.(, );
ufs.(, );
ufs.(, );
cout << << endl;
ufs.();
cout << << ufs.() << endl;
ufs.(, );
ufs.(, );
cout << << endl;
ufs.();
cout << << ufs.() << endl;
ufs.(, );
ufs.(, );
cout << << endl;
ufs.();
cout << << ufs.() << endl;
ufs.(, );
cout << << endl;
ufs.();
cout << << ufs.() << endl;
root9 = ufs.();
cout << << root9 << endl;
root3 = ufs.();
root7 = ufs.();
cout << << root3 << endl;
cout << << root7 << endl;
cout << << (root3 == root7 ? : ) << endl;
;
}
构造函数:接收集合大小
size,初始化_ufs数组为size个 -1,每个元素自成一个集合;FindRoot 函数:迭代实现路径压缩,分两步:①找到根节点;②将路径上所有元素的父指针指向根节点,确保下次查找更快;Union 函数:按集合大小合并,将较小集合合并到较大集合,避免树过深,提高查找效率;Count 函数:遍历数组统计负数个数,即集合个数;PrintUFS 函数:辅助调试,打印当前并查集数组状态。
除了迭代实现,FindRoot 也可以用递归实现路径压缩,代码更简洁:
// 递归实现查找(带路径压缩)
int FindRootRecursive(int index) {
if (index < 0 || index >= _ufs.size()) {
throw invalid_argument("index out of range");
}
// 递归终止条件:找到根节点(_ufs[index] < 0)
if (_ufs[index] < 0) {
return index;
}
// 路径压缩:将当前元素的父节点更新为根节点,递归查找
_ufs[index] = FindRootRecursive(_ufs[index]);
return _ufs[index];
}
递归实现的优点是代码简洁,但缺点是当集合元素较多、树较深时,可能会导致栈溢出(递归深度超过系统栈限制)。因此,实际开发中更推荐使用迭代实现。
并查集的应用非常广泛,尤其在图论、动态连通性问题中。下面我们结合两道 LeetCode 高频面试题,讲解并查集的实际应用。
题目链接:https://leetcode.cn/problems/number-of-provinces/description/
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。一个'省份'是由一组直接或间接相连的城市组成,组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,isConnected[i][j] = 0 表示不直接相连。返回矩阵中省份的数量。
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2
解释:有 2 个省份,[0,1] 和 [2]。
这道题本质上是求图的连通分量个数,用并查集可以轻松解决:
初始化并查集,每个城市自成一个集合;遍历矩阵**
isConnected,如果isConnected[i][j] = 1**(i 和 j 直接相连),则合并i和j所在的集合;最终并查集中的集合个数,就是省份的数量。
#include <vector>
using namespace std;
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
if (n == 0) {
return 0;
}
// 初始化并查集,n 个城市,每个城市初始为 -1
vector<int> ufs(n, -1);
// 查找函数(带路径压缩,lambda 表达式)
auto findRoot = [&ufs](int x) {
int root = x;
// 找到根节点
while (ufs[root] >= 0) {
root = ufs[root];
}
// 路径压缩
while (ufs[x] >= 0) {
int parent = ufs[x];
ufs[x] = root;
x = parent;
}
return root;
};
// 遍历矩阵,合并相连的城市
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
// j 从 i+1 开始,避免重复合并(i 和 j 与 j 和 i 是一样的)
if (isConnected[i][j] == 1) {
int root1 = (i);
root2 = (j);
(root1 != root2) {
(ufs[root1] > ufs[root2]) {
(root1, root2);
}
ufs[root1] += ufs[root2];
ufs[root2] = root1;
}
}
}
}
count = ;
( e : ufs) {
(e < ) {
++count;
}
}
count;
}
};
{
vector<vector<>> isConnected1 = {{,,},{,,},{,,}};
Solution sol;
cout << << sol.(isConnected1) << endl;
vector<vector<>> isConnected2 = {{,,},{,,},{,,}};
cout << << sol.(isConnected2) << endl;
;
}
遍历矩阵时,
j从i+1开始,避免重复处理(i,j)和(j,i),减少合并次数;查找函数使用迭代实现路径压缩,避免栈溢出;合并时按集合大小合并,优化树的高度。
题目链接:https://leetcode.cn/problems/satisfiability-of-equality-equations/description/
给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。只有当可以为变量分配整数的值,使得所有给定的方程都满足时,才返回 true,否则返回 false。
输入 1:["a==b","b!=a"]
输出 1:false
解释 1:"a==b" 和 "b!=a" 矛盾,无法同时满足。
输入 2:["a==b","b==c","a==c"]
输出 2:true
解释 2:所有方程都满足。
这道题的核心是**'相等关系具有传递性'**,可以用并查集来处理:
首先处理所有'=='方程:将相等的变量合并到同一个集合中(因为相等关系传递,a==b 且 b==c,则 a、b、c 在同一个集合);然后处理所有'!='方程:检查两个变量是否在同一个集合中。如果在,则矛盾,返回
false;如果不在,则满足条件;所有方程处理完毕后,返回true。
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
// 26 个小写字母,初始化并查集
vector<int> ufs(26, -1);
// 查找函数(带路径压缩)
auto findRoot = [&ufs](int x) {
int root = x;
while (ufs[root] >= 0) {
root = ufs[root];
}
// 路径压缩
while (ufs[x] >= 0) {
int parent = ufs[x];
ufs[x] = root;
x = parent;
}
return root;
};
// 第一步:处理所有"=="方程,合并相等的变量
for (const string& eq : equations) {
if (eq[1] == '=') {
// 是"=="方程
char c1 = eq[0];
char c2 = eq[3];
int x = c1 - 'a'; // 转换为 0-25 的索引
int y = c2 - 'a';
int root1 = (x);
root2 = (y);
(root1 != root2) {
(ufs[root1] > ufs[root2]) {
(root1, root2);
}
ufs[root1] += ufs[root2];
ufs[root2] = root1;
}
}
}
( string& eq : equations) {
(eq[] == ) {
c1 = eq[];
c2 = eq[];
x = c1 - ;
y = c2 - ;
root1 = (x);
root2 = (y);
(root1 == root2) {
;
}
}
}
;
}
};
{
vector<string> equations1 = {,};
Solution sol;
cout << (sol.(equations1) ? : ) << endl;
vector<string> equations2 = {,,};
cout << (sol.(equations2) ? : ) << endl;
vector<string> equations3 = {,,};
cout << (sol.(equations3) ? : ) << endl;
;
}
相等关系是传递的,适合用并查集合并;不等关系是直接的,只需检查两个变量是否在同一个集合即可;必须先处理所有'=='方程,再处理'!='方程,否则会出现逻辑错误(比如先处理'a!=b',再处理'a==b',此时无法发现矛盾)。
除了上述两道题,并查集还有很多经典应用:
最小生成树(Kruskal 算法):用并查集判断边的两个顶点是否在同一个集合,避免生成环;岛屿数量(LeetCode 200):可以用并查集合并相邻的陆地,最终统计集合个数;冗余连接(LeetCode 684):找到导致图中有环的边,用并查集判断边的两个顶点是否已连通;朋友圈问题:与省份数量类似,统计社交网络中的连通分量个数。
这些问题的核心思想都是**'动态连通性'**,并查集是解决这类问题的最优选择。
并查集的时间复杂度主要取决于**查找(Find)和合并(Union)**操作,经过路径压缩和按大小 / 秩合并优化后:
查找操作的均摊时间复杂度为 O(α(n)),其中 α 是阿克曼函数的反函数;合并操作的时间复杂度由查找操作决定,也是 O(α(n));统计集合个数的时间复杂度为 O(n),其中 n 是元素个数。
阿克曼函数 α(n) 增长极其缓慢,在实际应用中,α(n) 几乎可以看作是一个常数(对于 n < 10^60,α(n) ≤ 6)。因此,优化后的并查集可以看作是'近常数时间'的数据结构,效率极高。
并查集的空间复杂度为 O(n),其中 n 是元素个数,因为需要一个大小为 n 的数组存储父指针信息。
忘记边界检查:查找或合并时,元素索引可能超出数组范围,导致数组越界;路径压缩实现错误:递归实现时未考虑栈溢出,迭代实现时未正确更新父指针;合并时未按大小 / 秩合并:导致树的高度过高,查找效率退化;处理顺序错误:如等式方程问题中,先处理'!='再处理'==',导致无法发现矛盾;根节点判断错误:误将非负数当作根节点,或负数当作非根节点。
始终确保元素索引在合法范围内,必要时添加边界检查;优先使用迭代实现路径压缩,避免栈溢出;合并时务必按大小或秩合并,优化树的高度;根据问题逻辑,确定正确的处理顺序(如先合并后查询);牢记父指针数组的规则:负数是根节点,绝对值是集合大小;非负数是父节点索引。
并查集是一种简单而强大的数据结构,核心解决'动态连通性'问题,通过路径压缩和按大小 / 秩合并优化后,效率几乎达到常数级别。它的代码实现简洁,应用场景广泛,是面试中高频考察的知识点。
并查集的魅力在于其简洁的思想和高效的实现,掌握它不仅能帮助你轻松应对面试题,还能让你在处理实际问题时多一种高效的解决方案。希望本文能带你真正理解并查集,让这个强大的数据结构成为你的'编程利器'!

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online