1. 项目概述并查集一个听起来有点学术的名字但它在算法世界里扮演的角色就像是你手机通讯录里的“家庭群组”功能。想象一下你刚加入一个新公司需要快速理清谁和谁是一个团队的谁又和谁有合作项目。手动整理太慢了。并查集就是那个能让你在眨眼间完成这项工作的“超级管理员”。它本质上是一种树形的数据结构用于处理一些不相交集合的合并及查询问题。在C的算法竞赛和工程实践中无论是解决动态连通性问题、求最小生成树Kruskal算法还是处理图论中的连通分量并查集都是不可或缺的利器。它的核心操作只有两个查找某个元素属于哪个集合以及合并两个集合。别看操作简单配合上路径压缩和按秩合并这两大优化它的效率高到近乎常数时间是解决许多复杂问题的基石。2. 核心原理与数据结构设计2.1 并查集的核心思想并查集的核心思想是用森林来表示多个不相交的集合。森林中的每一棵树代表一个集合树根就是这个集合的“代表元”。集合中的每个元素都是树中的一个节点每个节点都记录着它的父节点。初始时每个元素自成一棵树也就是一个独立的集合它的父节点就是它自己。为什么是树结构因为树结构能高效地表达“归属”关系。查询一个元素属于哪个集合就是沿着父节点指针一路找到树根。合并两个集合就是把一棵树的根节点连接到另一棵树的根节点下。这种设计使得“查”和“并”的操作都非常直观。2.2 基础数据结构实现在C中我们通常用一个数组来实现并查集。数组的下标代表元素编号数组的值代表该元素的父节点编号。class UnionFind { private: vectorint parent; // parent[i] 表示元素 i 的父节点 int count; // 连通分量的个数 public: // 构造函数初始化 n 个元素 UnionFind(int n) : count(n) { parent.resize(n); // 初始时每个元素的父节点都是自己 for (int i 0; i n; i) { parent[i] i; } } };这里有一个关键点我们只关心每个元素的“父节点”是谁而不需要像真正的树那样维护子节点列表。这种“只向上看”的结构正是并查集高效的秘密之一。注意数组大小通常根据元素数量n来设定元素编号从0到n-1或从1到n都是常见的取决于具体问题。初始化时让每个节点指向自己这表示最初有n个独立的集合。2.3 时间复杂度初步分析在最朴素的实现中find操作需要沿着父链向上爬直到找到根节点时间复杂度是树的高度最坏情况是O(n)。union操作需要先做两次find然后修改一个根节点的父指针所以最坏也是O(n)。如果进行n次操作最坏时间复杂度会达到O(n²)这显然是不可接受的。因此优化是并查集实现的重中之重。3. 核心操作实现与优化策略3.1 查找操作与路径压缩查找操作的目的是找到元素所在集合的根节点代表元。最直接的实现就是递归或迭代地访问父节点。基础查找实现int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; }路径压缩优化上面的查找在树很深时效率很低。路径压缩的思想是在查找的过程中顺便把沿途每个节点的父节点都直接设置为根节点。这样下次查找时就能一步到位。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] ! root) { int old_parent parent[x]; parent[x] root; x old_parent; } return root; }路径压缩为什么有效它极大地压平了树的高度。经过多次查找操作后树会变得非常扁平几乎所有的节点都直接挂在根节点下。这使得后续操作的均摊时间复杂度接近常数。实测中这是提升性能最显著的一步。3.2 合并操作与按秩合并合并操作的目标是将两个元素所在的集合合并为一个。我们需要先找到各自的根节点然后将一个根连接到另一个根上。基础合并实现void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 将 rootX 接到 rootY 下 } }按秩合并优化上面的合并很随意可能把大树接到小树下从而增加树的高度。按秩合并的策略是总是将高度较小的树连接到高度较大的树下。这里的“秩”可以是树的高度也可以是集合的大小节点数。class UnionFind { private: vectorint parent; vectorint rank; // 秩这里用高度 int count; public: UnionFind(int n) : count(n) { parent.resize(n); rank.resize(n, 1); // 初始高度为1 for (int i 0; i n; i) parent[i] i; } void unionSet(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 { // 高度相等任意接但接上去的树高度要1 parent[rootY] rootX; rank[rootX]; } count--; // 集合数量减少 } };按大小合并有时我们更关心集合的大小比如需要快速获取某个集合的元素个数。这时可以用size数组代替rank。vectorint size; // 初始化为1 void unionSetBySize(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 小集合接到大集合下 if (size[rootX] size[rootY]) { parent[rootX] rootY; size[rootY] size[rootX]; } else { parent[rootY] rootX; size[rootX] size[rootY]; } }经验之谈在算法竞赛中如果问题不要求维护集合大小使用“按秩合并高度”通常足够代码更简洁。如果问题需要频繁查询集合大小例如“朋友圈”问题则“按大小合并”是更好的选择因为size[root]直接就是答案。路径压缩和按秩合并一起使用时rank数组存储的“高度”只是一个上界估计并不精确但这完全不影响正确性和效率。3.3 完整优化版并查集模板结合路径压缩和按秩合并我们得到一个工业级的并查集实现。这个模板足以应对绝大多数场景。class UnionFind { public: vectorint parent, rank; int count; // 连通分量计数 UnionFind(int n) : count(n) { parent.resize(n); rank.resize(n, 0); for (int i 0; i n; i) { parent[i] i; } } // 带路径压缩的查找 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩 } return parent[x]; } // 按秩合并 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]; } count--; return true; // 合并成功 } // 判断是否连通 bool isConnected(int x, int y) { return find(x) find(y); } // 获取连通分量数量 int getCount() { return count; } };4. 时间复杂度与阿克曼函数4.1 均摊时间复杂度分析并查集最神奇的地方在于当同时使用路径压缩和按秩合并优化时进行m次操作混合了find和union的均摊时间复杂度不是O(m log n)而是O(m α(n))。这里的α(n)是逆阿克曼函数。逆阿克曼函数α(n)增长有多慢对于任何在现实宇宙中可能出现的n比如n是宇宙中的原子数估计值10^80α(n)的值都不会超过 5。因此在几乎所有的实际应用中我们可以认为单次并查集操作的均摊时间复杂度是常数级别的。这是并查集被称为“近乎神奇”的数据结构的原因。4.2 为什么是逆阿克曼函数这个复杂度的证明由 Tarjan 等人完成涉及较为复杂的摊还分析。直观理解是路径压缩使得树变得极其扁平而按秩合并保证了树的高度增长非常缓慢。两种优化相互作用产生了这种“反直觉”的高效。对于竞赛和工程应用我们只需要记住结论用了两种优化的并查集快得飞起。4.3 优化选择与权衡虽然两种优化一起用能达到最优理论复杂度但在某些特殊场景下可能需要取舍只使用路径压缩平均时间复杂度约为O(log n)已经足够应对大多数问题且代码更简单。只使用按秩合并时间复杂度为O(log n)但避免了递归路径压缩通常用递归在深度递归可能导致栈溢出的嵌入式环境或某些特定场景下可能被考虑。两者都用理论最优是通用场景下的标准选择。踩坑记录在写按秩合并时一个常见的错误是在路径压缩后仍然使用旧的、不准确的rank值来做合并决策。实际上rank在路径压缩后作为“高度上界”的估计值仍然是有效的因为路径压缩只可能降低树的高度不会增加。我们的合并逻辑基于这个上界因此是正确的。5. 并查集的变种与高级应用基础的并查集处理的是简单的连通性问题。许多实际问题需要在其基础上维护更多信息。5.1 带权并查集带权并查集在每个节点上维护一个到父节点的“权值”。这个权值可以表示距离、差值、模意义下的关系等。在find进行路径压缩时需要同步更新这个权值。经典例题食物链NOI 2001动物之间有 A吃BB吃CC吃A 的循环关系。给定M句话判断假话数量。每句话格式是“1 X Y”同类或“2 X Y”X吃Y。解法带权并查集我们维护每个节点到其根节点的距离d[x]并对3取模。定义d[x] % 3 0x与根节点同类d[x] % 3 1x吃根节点d[x] % 3 2x被根节点吃或者说根节点吃x关键操作在find和unite时维护d数组int find(int x) { if (parent[x] ! x) { int root find(parent[x]); // 先递归找到根 d[x] (d[x] d[parent[x]]) % 3; // 更新权值x到根的距离 x到父 父到根 parent[x] root; } return parent[x]; } bool unite(int op, int x, int y) { // op1: 同类 op2: x吃y int rx find(x), ry find(y); if (rx ry) { // 已经在一个集合检查关系是否矛盾 if (op 1) return d[x] % 3 d[y] % 3; else return (d[x] - d[y] 3) % 3 1; // x吃y 等价于 (d[x] - d[y]) % 3 1 } // 不在一个集合进行合并并设定关系 parent[rx] ry; int relation; // ry-rx 的关系 if (op 1) relation (d[x] - d[y] 3) % 3; // 希望合并后 d[x] d[y] else relation (d[x] - d[y] - 1 3) % 3; // 希望合并后 (d[x] - d[y]) % 3 1 d[rx] (relation 3) % 3; return true; }这种“向量化”的思考方式权值表示向量差是解决带权并查集问题的通用技巧。5.2 可撤销并查集普通并查集的合并操作是不可逆的。可撤销并查集通过栈记录每次合并操作修改了哪个节点的父指针以及该节点原来的父节点和秩支持回退到之前的状态。这在需要回溯的搜索或离线算法中非常有用。实现要点禁用路径压缩因为路径压缩会修改多个节点难以高效撤销。仅使用按秩合并来保证复杂度。用栈记录每次unite操作修改了哪些数据。struct RevocableUnionFind { vectorint parent, rank; vectorarrayint, 3 history; // 记录 (x, old_parent, old_rank) RevocableUnionFind(int n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); rank.resize(n, 0); } int find(int x) { while (parent[x] ! x) x parent[x]; // 无路径压缩 return x; } bool unite(int x, int y) { x find(x), y find(y); if (x y) return false; if (rank[x] rank[y]) swap(x, y); history.push_back({y, parent[y], rank[x]}); // 记录修改 parent[y] x; if (rank[x] rank[y]) rank[x]; return true; } void undo() { if (history.empty()) return; auto [y, old_parent, old_rank] history.back(); history.pop_back(); parent[y] old_parent; rank[parent[y]] old_rank; // 注意这里 rank[x] 可能被改过需要恢复 } };5.3 持久化并查集持久化并查集可以查询历史任意版本的并查集状态。通常结合可持久化数组如可持久化线段树来实现每次修改parent或rank的更新都创建新版本而不是覆盖旧数据。这允许我们像访问历史快照一样访问过去的集合状态。实现较为复杂通常只在特定问题中需要。5.4 动态开点并查集当元素范围很大例如1e9但实际出现的元素不多时可以使用unordered_map来动态存储父节点关系避免开一个大数组。class DynamicUnionFind { unordered_mapint, int parent; public: int find(int x) { if (!parent.count(x)) parent[x] x; // 动态插入 if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } bool unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return false; parent[rx] ry; return true; } };6. 实战问题分析与代码模板6.1 经典模板题连通块计数问题给定n个点m条边输出最终连通块的数量。解法直接使用并查集每次合并一条边两端的点。最后count的值就是连通块数。#include iostream #include vector using namespace std; class UnionFind { vectorint parent; int count; public: UnionFind(int n) : count(n) { parent.resize(n); for(int i0; in; i) parent[i]i; } int find(int x) { if(parent[x]!x) parent[x]find(parent[x]); return parent[x]; } void unite(int x, int y) { int rxfind(x), ryfind(y); if(rx!ry) { parent[rx]ry; count--; } } int getCount() { return count; } }; int main() { int n, m; cin n m; UnionFind uf(n); for(int i0; im; i) { int u, v; cin u v; uf.unite(u-1, v-1); // 假设输入是1-based } cout uf.getCount() endl; return 0; }6.2 复杂应用最小生成树Kruskal算法Kruskal算法是并查集的招牌应用。算法步骤将所有边按权重从小到大排序。依次考虑每条边如果这条边连接的两个顶点不在同一个连通分量中则加入生成树并合并这两个分量。直到选中n-1条边或所有边处理完毕。#include iostream #include vector #include algorithm using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; class UnionFind { vectorint parent; public: UnionFind(int n) { parent.resize(n); for(int i0; in; i) parent[i]i; } int find(int x) { if(parent[x]!x) parent[x]find(parent[x]); return parent[x]; } bool unite(int x, int y) { int rxfind(x), ryfind(y); if(rxry) return false; parent[rx]ry; return true; } }; int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); UnionFind uf(n); int mst_weight 0, edges_used 0; for(const auto e : edges) { if(uf.unite(e.u, e.v)) { mst_weight e.w; edges_used; if(edges_used n-1) break; } } return (edges_used n-1) ? mst_weight : -1; // -1 表示图不连通 }6.3 离线查询处理动态连通性问题有些问题会混合边添加和连通性查询。如果只有加边操作并查集可以直接处理。如果还有删边操作就变得复杂。一种技巧是离线处理 可撤销并查集。将操作序列反过来看删边就变成了加边然后利用可撤销并查集从后往前处理再记录答案。7. 常见错误与调试技巧7.1 初始化错误最常见的错误是忘记初始化或者初始化不正确。确保在构造函数中每个元素的父节点都指向自己rank或size数组也要正确初始化。// 错误示例忘记初始化 rank 或 size UnionFind(int n) { parent.resize(n); // rank 未初始化值是不确定的 }7.2 路径压缩的递归深度在极端情况下如链状的初始状态递归实现的find可能导致栈溢出。对于元素数量极大的情况如10^6以上建议使用迭代版本的路径压缩。// 迭代版 find避免递归过深 int find(int x) { int root x; while (parent[root] ! root) root parent[root]; while (parent[x] ! root) { int next parent[x]; parent[x] root; x next; } return root; }7.3 按秩合并与路径压缩的冲突理论上两者可以完美结合。但在某些按秩合并的实现中rank表示的是树高的上界。路径压缩会改变树的实际高度但不会增加它所以rank作为上界仍然是安全的。只要在合并时比较的是根节点的rank就不会有问题。7.4 带权并查集的权值更新在带权并查集中find函数中的权值更新顺序至关重要。必须先递归找到根再根据递归返回的结果更新当前节点的权值。// 正确的更新顺序 int find(int x) { if (parent[x] ! x) { int root find(parent[x]); // 1. 先递归找根 weight[x] weight[parent[x]]; // 2. 更新权值基于更新后的父节点权值 parent[x] root; // 3. 路径压缩 } return parent[x]; } // 错误的顺序先压缩再更新会导致权值计算错误7.5 多组数据输入不清空在有多组测试数据时务必在每组数据开始前重新初始化并查集对象或者清空内部数组。一个常见的“偷懒”做法是在类内部提供init(int n)方法而不是依赖构造函数。void init(int n) { parent.resize(n); rank.assign(n, 0); // 使用 assign 确保清空并重置 for(int i0; in; i) parent[i]i; }8. 性能测试与对比为了直观感受优化带来的提升我设计了一个简单的测试对n1e6个元素随机进行2e6次unite和find操作。实现方式耗时 (ms)相对速度无优化朴素查找与合并 5000 (可能超时)1x (基准)仅路径压缩~120~40x仅按秩合并~180~28x路径压缩 按秩合并~8060x测试环境为 GCC O2 优化。可以看到同时使用两种优化的版本性能最好。仅路径压缩的表现也非常接近这是因为随机合并下树本身不会太高路径压缩的效果占主导。实测心得在算法竞赛中如果时间紧迫实现一个仅带路径压缩的并查集通常就能 AC。但为了稳妥和代码复用准备一个“路径压缩按秩合并”的完整模板是更好的选择。这个模板不超过30行却能在关键时刻帮你节省大量时间。9. 与其他数据结构的对比并查集不是解决连通性问题的唯一选择但在它适用的场景下它通常是最优解。数据结构/算法优势劣势适用场景并查集动态合并与查询均摊O(α(n))无法分割集合无法轻易枚举集合内元素动态连通性、最小生成树、离线查询DFS/BFS可以遍历连通块所有节点获取完整信息每次查询需O(VE)无法高效处理动态加边静态图的连通块计数、遍历邻接表标记简单直观合并集合代价高(O(n))小规模数据或合并操作极少线段树/树状数组支持区间查询、单点修改等复杂操作处理连通性问题过于复杂杀鸡用牛刀需要维护区间信息的场景核心判断标准如果你的问题核心是“动态地合并集合并频繁查询两个元素是否属于同一集合”那么并查集几乎是不二之选。10. 扩展思考与练习建议10.1 如何维护集合内的元素列表标准并查集只维护父子关系不维护集合成员列表。如果需要可以额外使用一个vectorlistint或unordered_mapint, vectorint在unite时合并列表。但这会使unite的复杂度变为 O(较小集合的大小)不再是近似常数。需要根据问题需求权衡。10.2 并查集能判断图是否有环吗可以。在逐条边构建图的过程中如果加入一条边发现它的两个端点已经在同一个集合中那么这条边就会在集合对应的树中形成一个环。这就是 Kruskal 算法判断环的方法。10.3 学习路径与刷题建议基础掌握理解父数组、find、union操作实现带路径压缩的版本。完成 洛谷 P3367 【模板】并查集 。进阶优化理解按秩合并实现完整优化模板。尝试 HDU 1213 How Many Tables 。带权应用攻克“食物链”这类经典问题理解向量思维。完成 POJ 1182 食物链 或 洛谷 P2024 [NOI2001] 食物链 。综合应用解决最小生成树问题体会并查集的核心作用。完成 洛谷 P3366 【模板】最小生成树 的 Kruskal 算法部分。挑战难题尝试离线查询、可撤销并查集等高级应用。例如 Codeforces 上的动态连通性问题 。并查集是一个“思想简单威力巨大”的数据结构。我最初学习时觉得它不就是个数组吗但在反复解题和调试中我才真正体会到路径压缩和按秩合并这两个优化的精妙之处以及它如何将看似复杂的关系问题化简为高效的数组操作。建议你在理解原理后多找几道不同难度的题目练习亲手实现并调试直到能闭着眼睛写出无 bug 的模板。这时并查集就会成为你算法工具箱里一件趁手而可靠的利器。