前言并查集Disjoint Set UnionDSU也叫 Union-Find是一种用来维护不相交集合的数据结构。它只干两件事把两个集合合并成一个union以及查询某个元素属于哪个集合find。听起来简单得不像话但配上两个小优化之后它的均摊复杂度低到几乎可以当成常数这让它成为图论算法里性价比最高的工具之一。常见的误解有三个。第一以为并查集「就是给每个元素记个编号」于是写成每次合并都遍历一遍改编号复杂度直接退化到平方级。第二以为「路径压缩和按秩合并随便用一个就行」——只用路径压缩的均摊复杂度是O(log n)只用按秩合并的最坏复杂度也是O(log n)两者同时用才有理论上的O(α(n))其中α是反阿克曼函数inverse Ackermann function对任何现实可及的输入规模它都不超过 4。第三以为并查集什么都能干——它不支持删除元素也不支持拆分集合。需要撤销的话得换成「可撤销并查集」此时不能做路径压缩需要拆分就得用更重的数据结构。本文从零讲清并查集的模型、两个优化的作用给出一个可直接使用的 C17 模板类最后用它解一道最小生成树的经典题。一、问题模型等价类与传递性并查集处理的是一种等价关系满足自反、对称、传递。典型场景无向图的连通分量a和b连通、b和c连通则a和c必然连通。等价类划分把一堆元素按某种规则归成若干互不相交的组。最小生成树Kruskal 算法判断加一条边会不会成环。网络节点分组、朋友圈、编译器里的类型等价分析。关键性质是不相交任意两个集合要么完全相同要么没有交集。正因为如此我们可以给每个集合选一个代表元representative——通常叫「根」。查询「在不在同一组」就退化成「根是不是同一个」。这就把问题简化成了如何维护每个元素指向根的那条链。二、朴素实现一棵不断长高的树最直接的做法每个元素记录自己的「父亲」根节点的父亲指向自己。#include iostream #include numeric #include vector // 朴素版本只做最简单的合并没有优化 class NaiveDSU { public: explicit NaiveDSU(int n) : parent_(n) { std::iota(parent_.begin(), parent_.end(), 0); } int find(int x) { while (parent_[x] ! x) x parent_[x]; return x; } void unite(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) parent_[rb] ra; // 直接把 rb 挂到 ra 下面 } private: std::vectorint parent_; }; int main() { NaiveDSU d(5); d.unite(0, 1); d.unite(1, 2); d.unite(2, 3); d.unite(3, 4); std::cout d.find(4) d.find(0) \n; // 同一个根 }std::iota定义在numeric把区间填充成0, 1, 2, ...正好用来做初始的「各自为政」。问题出在unite它总是把右树的根挂到左树的根上。如果按照unite(1,0); unite(2,1); unite(3,2); ...的顺序调用树会退化成一条链find每次都要走完整条链单次复杂度O(n)。连续做n次就是O(n²)——这就是「超时」的常见来源。两个优化的目标都是把树压矮。三、两个优化把树压矮优化一按秩合并union by rank或按大小合并union by size。合并时不要随便挂而是把「矮的树」挂到「高的树」下面。用rank记录树高的上界或直接用size记录元素个数每次把秩小的挂到秩大的上。只用这个优化树高就是O(log n)因为每次合并后被挂走的那棵树里的元素所在子树高度至少翻倍。优化二路径压缩path compression。find的时候顺手把沿途所有节点都直接指向根。这样下次再查同样一批节点一步到位。注意路径压缩会改变树的结构所以rank记录的不再是真实树高而只是一个「启发式权重」——这不影响正确性只是让rank的含义不再精确。两个优化用不用、用几个效果差别很大优化组合单次操作复杂度说明都不用最坏O(n)链状退化会超时只用路径压缩均摊O(log n)实现简单通常够用只用按秩合并最坏O(log n)树高有保证可配合可撤销两者都用均摊O(α(n))理论最优α(n)实际不超过 4上表是算法理论里的经典结论Tarjan 的分析属于数学结论而非某个实现的特性具体跑多快还取决于常数、内存访问模式等。注意「可撤销并查集」这个例外如果需要支持撤销回滚上一次合并就不能用路径压缩因为路径压缩会一次性改掉大量节点的父亲无法逐条恢复。此时只用按秩合并靠额外的栈记录每次合并改动了什么。四、完整模板实现下面是一个可直接拿去用的版本。find写成迭代式的路径压缩避免深链时递归爆栈。#include iostream #include numeric #include utility #include vector class DSU { public: explicit DSU(int n) : parent_(static_caststd::size_t(n)), rank_(static_caststd::size_t(n), 0), count_(n) { std::iota(parent_.begin(), parent_.end(), 0); } // 查找根同时做路径压缩迭代版不会爆栈 int find(int x) { int root x; while (parent_[static_caststd::size_t(root)] ! root) root parent_[static_caststd::size_t(root)]; // 第二趟把沿途节点全部直接连到根 while (parent_[static_caststd::size_t(x)] ! root) { int next parent_[static_caststd::size_t(x)]; parent_[static_caststd::size_t(x)] root; x next; } return root; } // 合并。返回 true 表示原本不在同一集合本次真的合并了 bool unite(int a, int b) { int ra find(a); int rb find(b); if (ra rb) return false; if (rank_[static_caststd::size_t(ra)] rank_[static_caststd::size_t(rb)]) std::swap(ra, rb); parent_[static_caststd::size_t(rb)] ra; if (rank_[static_caststd::size_t(ra)] rank_[static_caststd::size_t(rb)]) rank_[static_caststd::size_t(ra)]; --count_; return true; } bool connected(int a, int b) { return find(a) find(b); } // 当前集合个数 int count() const { return count_; } int size() const { return static_castint(parent_.size()); } private: std::vectorint parent_; std::vectorint rank_; int count_; }; int main() { DSU d(6); std::cout 初始集合数: d.count() \n; d.unite(0, 1); d.unite(1, 2); d.unite(3, 4); std::cout 合并后集合数: d.count() \n; // 6 - 3 3 std::cout std::boolalpha 0 和 2 连通: d.connected(0, 2) \n // true 0 和 3 连通: d.connected(0, 3) \n // false 重复合并返回: d.unite(0, 2) \n; // false std::cout 0 与 3 合并: d.unite(0, 3) \n; // true std::cout 此时集合数: d.count() \n; // 2 std::cout 0 和 4 现在连通: d.connected(0, 4) \n; }用std::vector下标时必须转成std::size_t否则在-Wsign-conversion下会报警告。如果嫌啰嗦可以把参数和成员统一改成std::size_t或把元素个数封进一个struct本文保留int是为了读起来贴近算法题的写法。unite返回布尔值是个实用的小设计Kruskal 算法正需要「这条边的两端是否已经连通」这个信息直接用它就能省掉一次connected调用。五、实战用 Kruskal 求最小生成树最小生成树Minimum Spanning TreeMST的 Kruskal 算法思路很直白把所有边按权值从小到大排序依次尝试加入如果这条边的两端已经在同一集合就跳过否则会成环否则加入并合并两个集合。判断成环正是并查集的拿手活。#include algorithm #include iostream #include numeric #include utility #include vector class DSU { public: explicit DSU(int n) : parent_(static_caststd::size_t(n)), rank_(static_caststd::size_t(n), 0) { std::iota(parent_.begin(), parent_.end(), 0); } int find(int x) { int root x; while (parent_[static_caststd::size_t(root)] ! root) root parent_[static_caststd::size_t(root)]; while (parent_[static_caststd::size_t(x)] ! root) { int next parent_[static_caststd::size_t(x)]; parent_[static_caststd::size_t(x)] root; x next; } return root; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; if (rank_[static_caststd::size_t(ra)] rank_[static_caststd::size_t(rb)]) std::swap(ra, rb); parent_[static_caststd::size_t(rb)] ra; if (rank_[static_caststd::size_t(ra)] rank_[static_caststd::size_t(rb)]) rank_[static_caststd::size_t(ra)]; return true; } private: std::vectorint parent_; std::vectorint rank_; }; struct Edge { int u, v, w; }; int main() { const int n 5; // 顶点 0..4 std::vectorEdge edges { {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2}, {2, 3, 4}, {3, 4, 2}, {1, 4, 6} }; std::sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); DSU dsu(n); int total 0; int used 0; std::vectorEdge chosen; for (const Edge e : edges) { if (dsu.unite(e.u, e.v)) { // 不在同一集合才加入 total e.w; chosen.push_back(e); if (used n - 1) break; // 选够 n-1 条边就停 } } std::cout MST 总权重: total \n; for (const Edge e : chosen) std::cout e.u - e.v : e.w \n; }排序是O(m log m)并查集部分接近线性所以 Kruskal 的总复杂度由排序主导。这里用 Lambda 做比较器是 C11 起就支持的通用写法。常见坑点坑点 1find忘了压缩或者压缩写错。// ❌ 递归版在链很长时会爆栈且这条语句只是「找到了」没有压缩 int find(int x) { return parent_[x] x ? x : parent_[x]; }// ✅ 递归压缩链极端深时有栈风险或本文的迭代双趟写法 int find(int x) { return parent_[x] x ? x : (parent_[x] find(parent_[x])); }坑点 2合并时挂反了方向。// ❌ 不看秩随手挂链表场景下退化到 O(n) 单次 void unite(int a, int b) { parent_[find(a)] find(b); }// ✅ 小秩挂到大秩下同时更新秩 bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; if (rank_[ra] rank_[rb]) std::swap(ra, rb); parent_[rb] ra; if (rank_[ra] rank_[rb]) rank_[ra]; return true; }坑点 3只比较元素本身而不是根。// ❌ 这样比的是「父亲是否相同」同一集合但深度不同的元素会被判成不连通 bool connected(int a, int b) { return parent_[a] parent_[b]; }// ✅ 必须比较根 bool connected(int a, int b) { return find(a) find(b); }坑点 4下标 1-based 与 0-based 混用。// ❌ 题目顶点是 1..n却按 0..n-1 开会越界 DSU dsu(n); dsu.unite(1, n); // n 越界UB// ✅ 1-based 就开 n1 个位置 DSU dsu(n 1); dsu.unite(1, n);坑点 5以为unite能「取消」。// ❌ 并查集没有拆分/删除操作这样做只会破坏结构 // dsu.unite(a, b); ... 后来想把 b 挪出去做不到// ✅ 需要撤销就用「可撤销并查集」按秩合并 操作栈且不能路径压缩 // 需要拆分则考虑 Link-Cut Tree 或离线分治坑点 6在带权并查集里路径压缩忘了同步更新权值。带权并查集维护「到根的距离」这类信息在压缩时必须把父节点到根的权值累加进来否则第二次查询就会算错。// ✅ 带权版本先递归拿到根再更新权值 int find(int x) { if (parent_[x] x) return x; int root find(parent_[x]); weight_[x] weight_[parent_[x]]; // 累加父亲到根的权值 return parent_[x] root; // 再压缩 }顺序不能颠倒必须先把weight_[parent_[x]]更新到「父亲到根」的正确值再累加给x。反过来写就会少算一段。坑点 7把根节点也压缩掉。// ❌ 让根指向别人破坏「根的父亲是自己」这条不变式 if (parent_[root] ! root) parent_[root] ...;// ✅ 根的父亲永远是自己find 的终止条件就是靠这一条坑点 8用并查集判有向图的环。并查集只处理无向连通性。用它去判有向图里是否有环会得到错误结论。// ❌ 有向边 a - b直接 unite(a, b) 判断结论无效// ✅ 有向图判环用拓扑排序Kahn或 DFS 三色标记总结要点结论核心操作find查根、unite合并均摊近似常数朴素实现复杂度最坏单次O(n)会退化路径压缩均摊O(log n)find时把沿途节点直连根按秩/按大小合并最坏O(log n)小树挂大树下两者合用均摊O(α(n))α(n)实际不超过 4不支持的操作删除元素、拆分集合可撤销场景用按秩合并 操作栈不能路径压缩典型应用连通分量、Kruskal 最小生成树、等价类划分并查集只有十几行核心代码却把「维护等价关系」这件事做到了接近最优。写的时候记住三件事find要压缩、unite要按秩、比较要比较根。剩下的都是应用层面的组合。