1. 项目概述为什么并查集是面试官的“心头好”如果你刷过一些算法题或者正在准备技术面试大概率会碰到“朋友圈”、“岛屿数量”、“连通网络的操作次数”这类题目。乍一看它们可能涉及图论、搜索但老手一眼就能看出这背后藏着一个高效且优雅的数据结构——并查集。它不像链表、栈、队列那样直观也不如红黑树、B树那样复杂但它在处理“动态连通性”问题上几乎是“降维打击”般的存在。简单来说并查集就是用来管理一群元素并快速回答“元素A和元素B是否属于同一个集合”以及“将元素A和元素B所在的集合合并”这两个核心问题的工具。在C的语境下实现并查集不仅考察你对基础数据结构的理解更考验你能否将抽象的逻辑转化为简洁、高效的代码以及你是否掌握了路径压缩、按秩合并这些关键的优化技巧。面试官喜欢它是因为它能在一个简单的框架内综合考察候选人的编码能力、算法优化思维和对时间复杂度分析的掌握。一个裸的并查集实现可能只需要20行代码但一个经过优化的、工业级的实现加上对各类变种题目的应对策略足以拉开候选人之间的差距。这篇文章我就从一个多年C开发者和面试官的角度带你彻底玩转并查集从最底层的原理掰开揉碎到用C实现一个健壮的模板类最后直击那些高频且易错的面试题让你下次遇到时能从容应对。2. 并查集核心原理深度拆解2.1 从生活场景理解“动态连通性”让我们先忘掉代码用几个生活化的例子来感受并查集要解决的问题。例子一社交网络中的好友关系。假设你注册了一个新社交App系统最初认为每个用户都是一个独立的“圈子”。当你和用户B成为好友时系统需要将你俩的圈子合并。之后用户C又和B成为好友那么C也会加入这个合并后的大圈子。系统需要能快速判断任意两个用户比如你和C是否间接属于同一个朋友圈即是否连通。例子二电路中的连通性检查。想象一块电路板上有许多节点元件引脚最初所有节点都不相连。工程师通过焊接导线将两个节点连接起来。他需要随时能检测任意两个节点之间是否通电即是否通过导线直接或间接相连。例子三网络中的计算机。一个局域网中有许多台电脑通过网线将它们两两连接。我们需要知道任意两台电脑是否在同一个子网内即能否通信。这些场景的共同点是有一组元素用户、节点、电脑元素之间的关系是“连接”或“属于同一组”。这种关系具有传递性如果A连BB连C则A连C。我们需要支持两种操作1.合并两个元素所在的组2.查询两个元素是否在同一组。这正是并查集的用武之地。2.2 数据结构设计如何用数组表示森林并查集的核心思想是用森林来表示不相交的集合。森林中的每一棵树代表一个集合树根就是这个集合的“代表元”。同一个集合中的任意两个元素它们所在的树的根节点必然相同。在C实现中我们最常用一个一维数组parent来代表这片森林。数组的下标对应每一个元素通常给元素编号为0到n-1数组的值parent[i]表示元素i的父节点。如果parent[i] i那么恭喜元素i就是它所在那棵树的根节点代表元。初始时每个元素自成一棵树所以parent[i] i。合并操作要合并元素x和y所在的集合我们只需要找到x的根rootX和y的根rootY然后将其中一个根的父亲设置为另一个根即可例如parent[rootX] rootY。这样两棵树就合并成了一棵。查找操作要判断x和y是否属于同一集合我们分别找到它们的根rootX和rootY然后判断rootX rootY是否成立。查找根节点的过程就是一个不断向上递归或迭代寻找父节点的过程直到找到parent[i] i的那个i。这个设计看似简单但存在一个严重问题如果合并时总是随意将一棵树接到另一棵树下经过多次操作后树可能会退化成一条长长的链。此时查找根节点的操作就会退化为 O(n) 的时间复杂度对于大量操作来说是无法接受的。2.3 两大优化利器路径压缩与按秩合并为了解决退化问题我们必须引入优化。这是并查集算法的精髓也是面试中必须讲清楚的点。2.3.1 路径压缩路径压缩的核心思想是“在查找的过程中顺手把树拍平”。具体来说在查找元素i的根节点时我们不仅返回根节点还会将查找路径上经过的所有节点的父节点都直接设置为根节点。递归实现清晰但可能有栈溢出风险:int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归查找并赋值 } return parent[x]; }迭代实现更安全:int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; // 先找到根 } // 第二次遍历进行路径压缩 while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }路径压缩后整个集合的树结构会无限接近于一个“星形”结构除了根节点所有节点都直接指向根。这使得后续的查找操作平均时间复杂度接近常数。2.3.2 按秩合并路径压缩主要优化了“查”而按秩合并则优化了“并”。它的目的是在合并两棵树时总是将“矮”的树接到“高”的树下从而避免树的高度增长过快。我们需要另一个数组rank或size来记录以每个节点为根的树的高度或大小。初始时每个节点的高度为0或1视定义而定。合并时比较两棵树的根节点rootX和rootY的秩如果rank[rootX] rank[rootY]则将rootX接到rootY下rootY的秩不变。如果rank[rootX] rank[rootY]则将rootY接到rootX下rootX的秩不变。如果rank[rootX] rank[rootY]则可以任意连接但被接上去的树的根的秩需要加1。因为两棵高度相同的树合并新树的高度必然增加1。void unionSets(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已在同一集合 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; // 或 parent[rootX] rootY; 均可 rank[rootX]; // 秩相同连接后高度1 } }注意“秩”并不完全等于树的精确高度尤其是在路径压缩之后。你可以把它理解为树高的一个上界。按秩合并保证了有n个元素的森林中树的高度不会超过O(log n)。当它与路径压缩结合时并查集操作的摊还时间复杂度可以达到惊人的O(α(n))其中α(n)是增长极其缓慢的反阿克曼函数对于任何实际应用中的n这个值都不会超过5因此可以认为是常数时间。3. C 实现一个工业级的并查集模板类理解了原理我们动手用C实现一个封装良好、功能完整的并查集类。这不仅是为了做题更是学习如何设计一个可复用的数据结构组件。3.1 类设计与接口定义一个好的类设计应该职责清晰、接口简洁、易于使用。我们将实现以下核心接口构造函数初始化指定数量的元素每个元素独立成集。find查找元素所在集合的根代表元。unite(或unionSets)合并两个元素所在的集合。connected判断两个元素是否连通。count返回当前集合的数量即连通分量的个数。此外我们还可以提供一些辅助接口如获取某个集合的大小。#include vector #include numeric // for iota class UnionFind { public: // 构造函数初始化 n 个元素 explicit UnionFind(int n) : parent(n), rank(n, 0), setCount(n) { // 初始化 parent[i] i std::iota(parent.begin(), parent.end(), 0); } // 查找元素 x 的根带路径压缩 int find(int x) { // 迭代式路径压缩 while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩的优化跳一步 x parent[x]; } return x; // 也可以使用递归式见上文 } // 合并元素 x 和 y 所在的集合 bool unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return false; // 已经连通合并失败 } // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } setCount--; // 集合数量减少1 return true; // 合并成功 } // 判断 x 和 y 是否连通 bool connected(int x, int y) { return find(x) find(y); } // 返回当前连通分量的数量 int count() const { return setCount; } // 可选获取元素 x 所在集合的大小需要额外维护 size 数组 // int getSetSize(int x) { ... } private: std::vectorint parent; // 父节点数组 std::vectorint rank; // 秩数组 int setCount; // 当前集合连通分量的数量 };3.2 关键实现细节与性能考量std::iota的使用在构造函数中我们用std::iota(parent.begin(), parent.end(), 0)来快速将parent数组初始化为[0, 1, 2, ..., n-1]。这比写一个 for 循环更简洁也体现了对标准库的熟练运用。迭代式路径压缩的微优化在find的迭代实现中我们使用了parent[x] parent[parent[x]]。这行代码意味着在向上查找的同时让当前节点x直接指向它的“祖父”节点。这是一种非递归的、一步到位的路径压缩虽然不如递归版本那样一次压缩整条路径彻底但在多次操作中其摊还效果是一样的且避免了递归开销和栈溢出风险是工程中更常用的写法。unite方法的返回值设计为返回bool类型非常实用。true表示成功合并原本不在一个集合false表示无需合并原本就在一个集合。这个返回值在解决一些特定问题时很有用例如计算最小生成树的Kruskal算法中只有当unite返回true时对应的边才会被加入树中。空间复杂度O(n)用于存储parent和rank数组。对于百万甚至千万级别的元素这个开销通常是可接受的。模板化扩展上面的类固定使用int作为元素类型。在实际应用中如果元素不是连续的整数索引我们可以考虑使用unordered_map来映射元素到索引或者直接实现一个模板类允许用户指定元素类型。但对于绝大多数算法题连续的int索引已经足够。4. 高频面试题实战解析与变种掌握了模板我们来攻克面试中最常见的几类并查集题目。我会带你分析题目如何“翻译”成并查集问题并指出其中的陷阱。4.1 基础连通性问题例题LeetCode 547. 省份数量题目描述有n个城市其中一些彼此相连另一些没有相连。如果城市a与城市b直接相连且城市b与城市c直接相连那么城市a与城市c间接相连。省份是一组直接或间接相连的城市。给你一个n x n的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连为0表示不直接相连。返回矩阵中省份的数量。解题思路 这就是并查集的经典应用。每个城市是一个元素。我们遍历矩阵的上三角或下三角因为矩阵是对称的对于每一对isConnected[i][j] 1的城市i和j执行一次unite(i, j)操作。遍历结束后并查集中集合的数量即setCount就是省份的数量。C实现要点class Solution { public: int findCircleNum(vectorvectorint isConnected) { int n isConnected.size(); UnionFind uf(n); for (int i 0; i n; i) { // 只需遍历 j i 的部分避免重复合并和自己合并 for (int j i 1; j n; j) { if (isConnected[i][j] 1) { uf.unite(i, j); } } } return uf.count(); } };注意这里我们直接使用了上面实现的UnionFind类。在面试中如果被要求手写你需要将类实现内联在解题代码中。遍历时从i1开始是因为矩阵是对称的且自己与自己连通无需操作这能减少一半的循环次数。4.2 动态连通性与离线查询例题LeetCode 399. 除法求值题目描述略这是一道中等难度的题。它给出了许多变量之间的除法关系如a / b 2.0然后查询任意两个变量之间的除法结果。如果无法确定则返回 -1.0。解题思路 这道题可以建模成一个带权并查集问题。每个变量是一个节点已知的除法等式a / b v可以看作在节点a和b之间建立了一条边边的权重为v。我们需要维护每个节点到其所在集合根节点的“权重积”。parent[i]记录节点i的父节点。weight[i]记录节点i到其父节点的权重即i / parent[i]的值。核心操作查找在find(x)进行路径压缩时需要同步更新weight[x]。假设查找路径是x - p - root压缩前weight[x] x/pweight[p] p/root。压缩后x直接指向root那么新的weight[x]应该等于(x/p) * (p/root) x/root。这是一个累积相乘的过程。合并给定a / b v我们找到rootA和rootB。如果它们不同需要合并。假设我们将rootA接到rootB下即parent[rootA] rootB。我们需要确定weight[rootA]即rootA / rootB的值。已知a / b va / rootA weightAb / rootB weightB。推导v a/b (a/rootA) * (rootA/rootB) * (rootB/b) weightA * (rootA/rootB) * (1/weightB)。所以rootA/rootB v * weightB / weightA。这个值就是weight[rootA]。C实现片段class Solution { vectorint parent; vectordouble weight; // weight[i] val(i) / val(parent[i]) public: Solution() {} int find(int x) { if (parent[x] ! x) { int origin parent[x]; parent[x] find(parent[x]); weight[x] * weight[origin]; // 关键更新权重 } return parent[x]; } void unite(int x, int y, double value) { int rootX find(x); int rootY find(y); if (rootX rootY) return; parent[rootX] rootY; // 推导公式weight[rootX] value * weight[y] / weight[x]; weight[rootX] value * weight[y] / weight[x]; } double isConnected(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) return -1.0; // 在同一集合则 x/y (x/root) / (y/root) weight[x] / weight[y] return weight[x] / weight[y]; } vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) { // 将字符串变量映射为整数索引 unordered_mapstring, int var2id; int id 0; // ... (映射逻辑) parent.resize(id); weight.resize(id, 1.0); iota(parent.begin(), parent.end(), 0); // 合并已知等式 for (int i 0; i equations.size(); i) { int a var2id[equations[i][0]]; int b var2id[equations[i][1]]; unite(a, b, values[i]); } // 处理查询 vectordouble ans; for (auto q : queries) { if (!var2id.count(q[0]) || !var2id.count(q[1])) { ans.push_back(-1.0); continue; } int a var2id[q[0]], b var2id[q[1]]; ans.push_back(isConnected(a, b)); } return ans; } };这道题是并查集应用的一个高峰它展示了并查集不仅能处理“是否连通”的布尔关系还能通过维护额外的信息权重来处理带比例的数值关系。理解其权重更新公式的推导是关键。4.3 二维网格与连通分量计数例题LeetCode 200. 岛屿数量题目描述给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。解题思路 DFS/BFS是更直观的解法但并查集同样可以解决且思路独特。我们将每个1的格子看作一个元素。遍历整个网格当遇到一个1时首先将其视为一个独立的岛屿集合。然后查看其上方和左侧的邻居因为遍历是从左上到右下查看已遍历过的邻居可以避免重复合并。如果邻居也是1则将当前格子与邻居格子进行合并。最终并查集中集合的数量就是岛屿的数量。注意需要将二维坐标(i, j)映射为一维索引通常用i * n jn为列数。C实现片段class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); UnionFind uf(m * n); int waterCount 0; // 记录水的格子数 vectorpairint, int dirs {{-1, 0}, {0, -1}}; // 只看上、左两个方向 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 0) { waterCount; continue; } int id i * n j; // 检查上方和左方的邻居 for (auto dir : dirs) { int ni i dir.first, nj j dir.second; if (ni 0 ni m nj 0 nj n grid[ni][nj] 1) { int nid ni * n nj; uf.unite(id, nid); } } } } // 集合总数 陆地连通分量数 水的格子数每个水格子自成一个集合 // 岛屿数 集合总数 - 水的格子数 return uf.count() - waterCount; // 更清晰的写法初始化时只加入陆地格子但需要额外处理索引映射略复杂。 } };实操心得在二维网格问题中使用并查集坐标到一维索引的映射是关键务必保证唯一且连续。另外合并时只需检查两个方向左上或右下即可覆盖所有相邻关系避免重复合并。这种方法的优势在于它是一种“在线”算法可以边读入数据边处理适合流式数据场景。但在一次性给全数据的题目中DFS/BFS在代码简洁性和常数时间上可能更有优势。5. 常见“坑点”与调试技巧实录即使理解了原理在实际编码和解题时依然会踩到一些坑。下面是我在面试辅导和实际开发中总结的几个高频问题。5.1 初始化与索引越界问题在构造函数中parent和rank数组的大小是n表示元素编号从0到n-1。但在解题时我们有时会因为疏忽使用了等于n或负数的索引去调用find或unite。案例在二维网格问题中计算邻居坐标(ni, nj)时如果忘记检查边界ni 0 ni m就可能产生越界索引进而访问parent数组越界导致运行时错误或内存错误。排查技巧在find和unite函数入口处可以添加断言assert(x 0 x parent.size())来快速定位问题。在竞赛或面试中至少在心里要过一遍索引的合法性。对于二维映射一维的公式id i * col j要反复确认col是列数并且i, j在有效范围内。5.2 路径压缩与按秩合并的协同工作问题在同时使用路径压缩和按秩合并时rank数组的含义变得有些“不精确”。路径压缩会改变树的结构但rank值在压缩后并不会更新。这会影响按秩合并的判断吗答案不会。这正是“秩”的精妙之处。我们并不需要rank记录精确的高度只需要它作为一个“上界”或“估计值”。按秩合并的逻辑保证了即使经过路径压缩以rank值较小的根去链接到值较大的根依然能有效控制树高的增长。在摊还分析中这种组合被证明是高效的。所以在代码中我们永远不要在find函数中去修改rank值。5.3 并查集无法处理“断开连接”操作问题并查集擅长合并和查询但不支持将已合并的集合拆分开即“断开”操作。这是一个根本性的限制。案例有这样一个问题“设计一个数据结构支持连接两个节点、断开两个节点、查询两个节点是否连通。” 并查集无法高效支持“断开”。如果需要支持断开可能需要使用更复杂的数据结构如动态图或线段树分治。应对策略在面试中如果题目隐含了“断开”操作要立刻意识到并查集可能不是最佳选择或者需要将问题转化为离线查询所有断开操作已知使用“时光倒流”并查集的方法。5.4 复杂问题中的状态维护问题像“除法求值”这类带权并查集问题权重更新公式容易推导错误。或者在处理更复杂的状态如需要维护集合大小、集合内元素列表时逻辑容易混乱。调试技巧小数据手工模拟用纸笔画出3-5个节点手动执行合并和查找操作一步步更新parent和weight数组。这是发现公式错误最有效的方法。单元测试为你实现的UnionFind类编写简单的测试用例。例如测试连续合并后连通性是否正确测试带权并查集在简单等式下的计算结果。可视化输出在调试时可以写一个辅助函数打印出当前的parent和weight数组与手工模拟的结果对比。5.5 时间复杂度表述面试常问“并查集操作的时间复杂度是多少”标准回答对于同时使用了路径压缩和按秩合并优化的并查集单次find或unite操作的摊还时间复杂度是O(α(n))其中α(n)是反阿克曼函数。对于任何在现实宇宙中有意义的n比如n小于宇宙中原子的总数α(n)都不会超过5因此在实际应用中可以被认为是常数时间复杂度。不要只说“平均是O(1)”虽然意思接近但“摊还O(α(n))”更能体现你的知识深度。如果只实现了路径压缩或按秩合并之一时间复杂度是O(log n)。如果都没优化最坏是O(n)。并查集是一个“原理简单细节微妙应用广泛”的数据结构。吃透它的实现理解其优化原理并熟练应用于各类连通性问题能让你在解决算法问题和应对技术面试时多一把犀利的武器。最后记住多写多练把模板和经典题目的解法变成肌肉记忆当你再看到“连通”、“分组”、“关系传递”这些关键词时并查集就应该成为你脑海中的第一反应。
1. 项目概述为什么并查集是面试官的“心头好”如果你刷过一些算法题或者正在准备技术面试大概率会碰到“朋友圈”、“岛屿数量”、“连通网络的操作次数”这类题目。乍一看它们可能涉及图论、搜索但老手一眼就能看出这背后藏着一个高效且优雅的数据结构——并查集。它不像链表、栈、队列那样直观也不如红黑树、B树那样复杂但它在处理“动态连通性”问题上几乎是“降维打击”般的存在。简单来说并查集就是用来管理一群元素并快速回答“元素A和元素B是否属于同一个集合”以及“将元素A和元素B所在的集合合并”这两个核心问题的工具。在C的语境下实现并查集不仅考察你对基础数据结构的理解更考验你能否将抽象的逻辑转化为简洁、高效的代码以及你是否掌握了路径压缩、按秩合并这些关键的优化技巧。面试官喜欢它是因为它能在一个简单的框架内综合考察候选人的编码能力、算法优化思维和对时间复杂度分析的掌握。一个裸的并查集实现可能只需要20行代码但一个经过优化的、工业级的实现加上对各类变种题目的应对策略足以拉开候选人之间的差距。这篇文章我就从一个多年C开发者和面试官的角度带你彻底玩转并查集从最底层的原理掰开揉碎到用C实现一个健壮的模板类最后直击那些高频且易错的面试题让你下次遇到时能从容应对。2. 并查集核心原理深度拆解2.1 从生活场景理解“动态连通性”让我们先忘掉代码用几个生活化的例子来感受并查集要解决的问题。例子一社交网络中的好友关系。假设你注册了一个新社交App系统最初认为每个用户都是一个独立的“圈子”。当你和用户B成为好友时系统需要将你俩的圈子合并。之后用户C又和B成为好友那么C也会加入这个合并后的大圈子。系统需要能快速判断任意两个用户比如你和C是否间接属于同一个朋友圈即是否连通。例子二电路中的连通性检查。想象一块电路板上有许多节点元件引脚最初所有节点都不相连。工程师通过焊接导线将两个节点连接起来。他需要随时能检测任意两个节点之间是否通电即是否通过导线直接或间接相连。例子三网络中的计算机。一个局域网中有许多台电脑通过网线将它们两两连接。我们需要知道任意两台电脑是否在同一个子网内即能否通信。这些场景的共同点是有一组元素用户、节点、电脑元素之间的关系是“连接”或“属于同一组”。这种关系具有传递性如果A连BB连C则A连C。我们需要支持两种操作1.合并两个元素所在的组2.查询两个元素是否在同一组。这正是并查集的用武之地。2.2 数据结构设计如何用数组表示森林并查集的核心思想是用森林来表示不相交的集合。森林中的每一棵树代表一个集合树根就是这个集合的“代表元”。同一个集合中的任意两个元素它们所在的树的根节点必然相同。在C实现中我们最常用一个一维数组parent来代表这片森林。数组的下标对应每一个元素通常给元素编号为0到n-1数组的值parent[i]表示元素i的父节点。如果parent[i] i那么恭喜元素i就是它所在那棵树的根节点代表元。初始时每个元素自成一棵树所以parent[i] i。合并操作要合并元素x和y所在的集合我们只需要找到x的根rootX和y的根rootY然后将其中一个根的父亲设置为另一个根即可例如parent[rootX] rootY。这样两棵树就合并成了一棵。查找操作要判断x和y是否属于同一集合我们分别找到它们的根rootX和rootY然后判断rootX rootY是否成立。查找根节点的过程就是一个不断向上递归或迭代寻找父节点的过程直到找到parent[i] i的那个i。这个设计看似简单但存在一个严重问题如果合并时总是随意将一棵树接到另一棵树下经过多次操作后树可能会退化成一条长长的链。此时查找根节点的操作就会退化为 O(n) 的时间复杂度对于大量操作来说是无法接受的。2.3 两大优化利器路径压缩与按秩合并为了解决退化问题我们必须引入优化。这是并查集算法的精髓也是面试中必须讲清楚的点。2.3.1 路径压缩路径压缩的核心思想是“在查找的过程中顺手把树拍平”。具体来说在查找元素i的根节点时我们不仅返回根节点还会将查找路径上经过的所有节点的父节点都直接设置为根节点。递归实现清晰但可能有栈溢出风险:int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归查找并赋值 } return parent[x]; }迭代实现更安全:int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; // 先找到根 } // 第二次遍历进行路径压缩 while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }路径压缩后整个集合的树结构会无限接近于一个“星形”结构除了根节点所有节点都直接指向根。这使得后续的查找操作平均时间复杂度接近常数。2.3.2 按秩合并路径压缩主要优化了“查”而按秩合并则优化了“并”。它的目的是在合并两棵树时总是将“矮”的树接到“高”的树下从而避免树的高度增长过快。我们需要另一个数组rank或size来记录以每个节点为根的树的高度或大小。初始时每个节点的高度为0或1视定义而定。合并时比较两棵树的根节点rootX和rootY的秩如果rank[rootX] rank[rootY]则将rootX接到rootY下rootY的秩不变。如果rank[rootX] rank[rootY]则将rootY接到rootX下rootX的秩不变。如果rank[rootX] rank[rootY]则可以任意连接但被接上去的树的根的秩需要加1。因为两棵高度相同的树合并新树的高度必然增加1。void unionSets(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已在同一集合 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; // 或 parent[rootX] rootY; 均可 rank[rootX]; // 秩相同连接后高度1 } }注意“秩”并不完全等于树的精确高度尤其是在路径压缩之后。你可以把它理解为树高的一个上界。按秩合并保证了有n个元素的森林中树的高度不会超过O(log n)。当它与路径压缩结合时并查集操作的摊还时间复杂度可以达到惊人的O(α(n))其中α(n)是增长极其缓慢的反阿克曼函数对于任何实际应用中的n这个值都不会超过5因此可以认为是常数时间。3. C 实现一个工业级的并查集模板类理解了原理我们动手用C实现一个封装良好、功能完整的并查集类。这不仅是为了做题更是学习如何设计一个可复用的数据结构组件。3.1 类设计与接口定义一个好的类设计应该职责清晰、接口简洁、易于使用。我们将实现以下核心接口构造函数初始化指定数量的元素每个元素独立成集。find查找元素所在集合的根代表元。unite(或unionSets)合并两个元素所在的集合。connected判断两个元素是否连通。count返回当前集合的数量即连通分量的个数。此外我们还可以提供一些辅助接口如获取某个集合的大小。#include vector #include numeric // for iota class UnionFind { public: // 构造函数初始化 n 个元素 explicit UnionFind(int n) : parent(n), rank(n, 0), setCount(n) { // 初始化 parent[i] i std::iota(parent.begin(), parent.end(), 0); } // 查找元素 x 的根带路径压缩 int find(int x) { // 迭代式路径压缩 while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩的优化跳一步 x parent[x]; } return x; // 也可以使用递归式见上文 } // 合并元素 x 和 y 所在的集合 bool unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return false; // 已经连通合并失败 } // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } setCount--; // 集合数量减少1 return true; // 合并成功 } // 判断 x 和 y 是否连通 bool connected(int x, int y) { return find(x) find(y); } // 返回当前连通分量的数量 int count() const { return setCount; } // 可选获取元素 x 所在集合的大小需要额外维护 size 数组 // int getSetSize(int x) { ... } private: std::vectorint parent; // 父节点数组 std::vectorint rank; // 秩数组 int setCount; // 当前集合连通分量的数量 };3.2 关键实现细节与性能考量std::iota的使用在构造函数中我们用std::iota(parent.begin(), parent.end(), 0)来快速将parent数组初始化为[0, 1, 2, ..., n-1]。这比写一个 for 循环更简洁也体现了对标准库的熟练运用。迭代式路径压缩的微优化在find的迭代实现中我们使用了parent[x] parent[parent[x]]。这行代码意味着在向上查找的同时让当前节点x直接指向它的“祖父”节点。这是一种非递归的、一步到位的路径压缩虽然不如递归版本那样一次压缩整条路径彻底但在多次操作中其摊还效果是一样的且避免了递归开销和栈溢出风险是工程中更常用的写法。unite方法的返回值设计为返回bool类型非常实用。true表示成功合并原本不在一个集合false表示无需合并原本就在一个集合。这个返回值在解决一些特定问题时很有用例如计算最小生成树的Kruskal算法中只有当unite返回true时对应的边才会被加入树中。空间复杂度O(n)用于存储parent和rank数组。对于百万甚至千万级别的元素这个开销通常是可接受的。模板化扩展上面的类固定使用int作为元素类型。在实际应用中如果元素不是连续的整数索引我们可以考虑使用unordered_map来映射元素到索引或者直接实现一个模板类允许用户指定元素类型。但对于绝大多数算法题连续的int索引已经足够。4. 高频面试题实战解析与变种掌握了模板我们来攻克面试中最常见的几类并查集题目。我会带你分析题目如何“翻译”成并查集问题并指出其中的陷阱。4.1 基础连通性问题例题LeetCode 547. 省份数量题目描述有n个城市其中一些彼此相连另一些没有相连。如果城市a与城市b直接相连且城市b与城市c直接相连那么城市a与城市c间接相连。省份是一组直接或间接相连的城市。给你一个n x n的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连为0表示不直接相连。返回矩阵中省份的数量。解题思路 这就是并查集的经典应用。每个城市是一个元素。我们遍历矩阵的上三角或下三角因为矩阵是对称的对于每一对isConnected[i][j] 1的城市i和j执行一次unite(i, j)操作。遍历结束后并查集中集合的数量即setCount就是省份的数量。C实现要点class Solution { public: int findCircleNum(vectorvectorint isConnected) { int n isConnected.size(); UnionFind uf(n); for (int i 0; i n; i) { // 只需遍历 j i 的部分避免重复合并和自己合并 for (int j i 1; j n; j) { if (isConnected[i][j] 1) { uf.unite(i, j); } } } return uf.count(); } };注意这里我们直接使用了上面实现的UnionFind类。在面试中如果被要求手写你需要将类实现内联在解题代码中。遍历时从i1开始是因为矩阵是对称的且自己与自己连通无需操作这能减少一半的循环次数。4.2 动态连通性与离线查询例题LeetCode 399. 除法求值题目描述略这是一道中等难度的题。它给出了许多变量之间的除法关系如a / b 2.0然后查询任意两个变量之间的除法结果。如果无法确定则返回 -1.0。解题思路 这道题可以建模成一个带权并查集问题。每个变量是一个节点已知的除法等式a / b v可以看作在节点a和b之间建立了一条边边的权重为v。我们需要维护每个节点到其所在集合根节点的“权重积”。parent[i]记录节点i的父节点。weight[i]记录节点i到其父节点的权重即i / parent[i]的值。核心操作查找在find(x)进行路径压缩时需要同步更新weight[x]。假设查找路径是x - p - root压缩前weight[x] x/pweight[p] p/root。压缩后x直接指向root那么新的weight[x]应该等于(x/p) * (p/root) x/root。这是一个累积相乘的过程。合并给定a / b v我们找到rootA和rootB。如果它们不同需要合并。假设我们将rootA接到rootB下即parent[rootA] rootB。我们需要确定weight[rootA]即rootA / rootB的值。已知a / b va / rootA weightAb / rootB weightB。推导v a/b (a/rootA) * (rootA/rootB) * (rootB/b) weightA * (rootA/rootB) * (1/weightB)。所以rootA/rootB v * weightB / weightA。这个值就是weight[rootA]。C实现片段class Solution { vectorint parent; vectordouble weight; // weight[i] val(i) / val(parent[i]) public: Solution() {} int find(int x) { if (parent[x] ! x) { int origin parent[x]; parent[x] find(parent[x]); weight[x] * weight[origin]; // 关键更新权重 } return parent[x]; } void unite(int x, int y, double value) { int rootX find(x); int rootY find(y); if (rootX rootY) return; parent[rootX] rootY; // 推导公式weight[rootX] value * weight[y] / weight[x]; weight[rootX] value * weight[y] / weight[x]; } double isConnected(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) return -1.0; // 在同一集合则 x/y (x/root) / (y/root) weight[x] / weight[y] return weight[x] / weight[y]; } vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) { // 将字符串变量映射为整数索引 unordered_mapstring, int var2id; int id 0; // ... (映射逻辑) parent.resize(id); weight.resize(id, 1.0); iota(parent.begin(), parent.end(), 0); // 合并已知等式 for (int i 0; i equations.size(); i) { int a var2id[equations[i][0]]; int b var2id[equations[i][1]]; unite(a, b, values[i]); } // 处理查询 vectordouble ans; for (auto q : queries) { if (!var2id.count(q[0]) || !var2id.count(q[1])) { ans.push_back(-1.0); continue; } int a var2id[q[0]], b var2id[q[1]]; ans.push_back(isConnected(a, b)); } return ans; } };这道题是并查集应用的一个高峰它展示了并查集不仅能处理“是否连通”的布尔关系还能通过维护额外的信息权重来处理带比例的数值关系。理解其权重更新公式的推导是关键。4.3 二维网格与连通分量计数例题LeetCode 200. 岛屿数量题目描述给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。解题思路 DFS/BFS是更直观的解法但并查集同样可以解决且思路独特。我们将每个1的格子看作一个元素。遍历整个网格当遇到一个1时首先将其视为一个独立的岛屿集合。然后查看其上方和左侧的邻居因为遍历是从左上到右下查看已遍历过的邻居可以避免重复合并。如果邻居也是1则将当前格子与邻居格子进行合并。最终并查集中集合的数量就是岛屿的数量。注意需要将二维坐标(i, j)映射为一维索引通常用i * n jn为列数。C实现片段class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); UnionFind uf(m * n); int waterCount 0; // 记录水的格子数 vectorpairint, int dirs {{-1, 0}, {0, -1}}; // 只看上、左两个方向 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 0) { waterCount; continue; } int id i * n j; // 检查上方和左方的邻居 for (auto dir : dirs) { int ni i dir.first, nj j dir.second; if (ni 0 ni m nj 0 nj n grid[ni][nj] 1) { int nid ni * n nj; uf.unite(id, nid); } } } } // 集合总数 陆地连通分量数 水的格子数每个水格子自成一个集合 // 岛屿数 集合总数 - 水的格子数 return uf.count() - waterCount; // 更清晰的写法初始化时只加入陆地格子但需要额外处理索引映射略复杂。 } };实操心得在二维网格问题中使用并查集坐标到一维索引的映射是关键务必保证唯一且连续。另外合并时只需检查两个方向左上或右下即可覆盖所有相邻关系避免重复合并。这种方法的优势在于它是一种“在线”算法可以边读入数据边处理适合流式数据场景。但在一次性给全数据的题目中DFS/BFS在代码简洁性和常数时间上可能更有优势。5. 常见“坑点”与调试技巧实录即使理解了原理在实际编码和解题时依然会踩到一些坑。下面是我在面试辅导和实际开发中总结的几个高频问题。5.1 初始化与索引越界问题在构造函数中parent和rank数组的大小是n表示元素编号从0到n-1。但在解题时我们有时会因为疏忽使用了等于n或负数的索引去调用find或unite。案例在二维网格问题中计算邻居坐标(ni, nj)时如果忘记检查边界ni 0 ni m就可能产生越界索引进而访问parent数组越界导致运行时错误或内存错误。排查技巧在find和unite函数入口处可以添加断言assert(x 0 x parent.size())来快速定位问题。在竞赛或面试中至少在心里要过一遍索引的合法性。对于二维映射一维的公式id i * col j要反复确认col是列数并且i, j在有效范围内。5.2 路径压缩与按秩合并的协同工作问题在同时使用路径压缩和按秩合并时rank数组的含义变得有些“不精确”。路径压缩会改变树的结构但rank值在压缩后并不会更新。这会影响按秩合并的判断吗答案不会。这正是“秩”的精妙之处。我们并不需要rank记录精确的高度只需要它作为一个“上界”或“估计值”。按秩合并的逻辑保证了即使经过路径压缩以rank值较小的根去链接到值较大的根依然能有效控制树高的增长。在摊还分析中这种组合被证明是高效的。所以在代码中我们永远不要在find函数中去修改rank值。5.3 并查集无法处理“断开连接”操作问题并查集擅长合并和查询但不支持将已合并的集合拆分开即“断开”操作。这是一个根本性的限制。案例有这样一个问题“设计一个数据结构支持连接两个节点、断开两个节点、查询两个节点是否连通。” 并查集无法高效支持“断开”。如果需要支持断开可能需要使用更复杂的数据结构如动态图或线段树分治。应对策略在面试中如果题目隐含了“断开”操作要立刻意识到并查集可能不是最佳选择或者需要将问题转化为离线查询所有断开操作已知使用“时光倒流”并查集的方法。5.4 复杂问题中的状态维护问题像“除法求值”这类带权并查集问题权重更新公式容易推导错误。或者在处理更复杂的状态如需要维护集合大小、集合内元素列表时逻辑容易混乱。调试技巧小数据手工模拟用纸笔画出3-5个节点手动执行合并和查找操作一步步更新parent和weight数组。这是发现公式错误最有效的方法。单元测试为你实现的UnionFind类编写简单的测试用例。例如测试连续合并后连通性是否正确测试带权并查集在简单等式下的计算结果。可视化输出在调试时可以写一个辅助函数打印出当前的parent和weight数组与手工模拟的结果对比。5.5 时间复杂度表述面试常问“并查集操作的时间复杂度是多少”标准回答对于同时使用了路径压缩和按秩合并优化的并查集单次find或unite操作的摊还时间复杂度是O(α(n))其中α(n)是反阿克曼函数。对于任何在现实宇宙中有意义的n比如n小于宇宙中原子的总数α(n)都不会超过5因此在实际应用中可以被认为是常数时间复杂度。不要只说“平均是O(1)”虽然意思接近但“摊还O(α(n))”更能体现你的知识深度。如果只实现了路径压缩或按秩合并之一时间复杂度是O(log n)。如果都没优化最坏是O(n)。并查集是一个“原理简单细节微妙应用广泛”的数据结构。吃透它的实现理解其优化原理并熟练应用于各类连通性问题能让你在解决算法问题和应对技术面试时多一把犀利的武器。最后记住多写多练把模板和经典题目的解法变成肌肉记忆当你再看到“连通”、“分组”、“关系传递”这些关键词时并查集就应该成为你脑海中的第一反应。
