)
前言并查集(disjoint set union, DSU)维护一组互不相交的集合,支持两种操作:查询某个元素属于哪个集合,以及合并两个集合。朴素实现里,合并时随意把一棵树挂到另一棵下面,树可能退化成一条链,单次查询的最坏代价是 O(n)。两种经典优化针对的正是这一点:按大小合并(union by size)与按秩合并(union by rank),它们都保证树高保持在 O(log n);再叠加路径压缩(path compression),均摊代价降到反阿克曼函数 α(n),在实践中可以视为常数。最常见的误解是把「路径压缩」和「按大小合并」当成二选一。实际上两者解决的是不同问题:路径压缩缩短的是「已经访问过的路径」,它不改变合并策略;按大小/秩合并控制的是「合并时树的形状」,它保证即使不做压缩,树也不会太高。只用路径压缩,均摊复杂度是 O(log n);只用按大小合并,最坏是 O(log n);两者一起用才有 O(α(n)) 的结论。第二个误解是认为「按秩合并」里的秩就是树高。秩(rank)只是一个上界性质的启发值,路径压缩之后它甚至不再等于真实高度,但它作为合并依据仍然有效。第三个误解是在按大小合并时,把size存在非根节点上并在压缩后继续使用——size只在根节点有意义,合并后非根节点的值就过期了。本文先讲两种优化的原理与差别,再给出带路径压缩的完整实现,然后讨论常见变体与适用场景,最后列出八个易错点。示例以 C17 为基准,只依赖标准库。一、朴素并查集为什么会退化用parent[i]表示节点i的父节点,根节点的父节点指向自己。查询就是从节点一路走到根;合并就是把一个根的父亲改成另一个根。若合并顺序恰好是把长链挂到单节点上,树会越来越深,单次查询 O(n),n次操作就是 O(n²)。有两种思路可以限制树高。第一种是合并时做选择:总是把「较小」的树挂到「较大」的树下,这样任何节点的深度最多翻倍增长,树高是 O(log n)。第二种是查询时做压缩:把路径上所有节点直接连到根,后续查询就是 O(1)。两者正交,可以同时使用。二、按大小合并与按秩合并按大小合并(union by size)维护每棵树包含的节点数,只对根节点有效。合并两个根ra、rb时,把节点数少的根挂到节点数多的根下,并把两个计数相加写到新的根上。由于每次合并至少让较小树的规模翻倍,任何节点的深度不超过 O(log n)。按秩合并(union by rank)维护一个「秩」,初始为 0。合并时把秩小的根挂到秩大的根下;只有两棵树的秩相等时,新根的秩才加一。秩的含义是「树高的一个上界」,不是精确高度。它的优点是只需要一个很小的整数,不必维护节点数;缺点是当两棵树秩不等但规模相差很大时,它不会像按大小那样精确地选择。两者在渐进复杂度上没有区别,工程上按大小更直观,也便于额外回答「某个集合有多大」这类问题;按秩则节省一点内存(秩通常用unsigned char就够)。选择哪一个更多是接口需求决定的。三、路径压缩的写法路径压缩有两种常见写法。递归版最简洁:查询时先递归找到根,回溯时把当前节点的父节点直接改成根。它的递归深度等于树高,在同时使用按大小/秩合并时是 O(log n),一般不会爆栈;但如果只用路径压缩、不做合并优化,树高可能到 O(n),递归就有栈溢出的风险。迭代版分两趟:第一趟沿父指针走到根,第二趟从原节点再走一遍,把沿途节点的父节点都改成根。也可以写成「路径减半」:每走一步把当前节点的父节点改成祖父节点,只遍历一趟,压缩效果略弱但代码短。路径压缩不改变集合的划分,只改变表示方式,因此可以在查询过程中安全地修改parent。但它会破坏「父节点编号小于子节点」之类原本可能存在的性质,不要依赖遍历顺序。四、完整示例下面的实现同时支持按大小与按秩两种策略,用模板参数或枚举切换都行;这里用两个独立的类,便于对照。两者都带路径压缩与连通分量计数。// 适用于 C17#include iostream#include numeric#include stdexcept#include vectorclass DsuBySize {public:explicit DsuBySize(int n): parent_(checkedSize(n)),size_(checkedSize(n), 1),components_(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) {const 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);int rb find(b);if (ra rb) {return false;}if (size_[static_caststd::size_t(ra)] size_[static_caststd::size_t(rb)]) {std::swap(ra, rb);}parent_[static_caststd::size_t(rb)] ra;size_[static_caststd::size_t(ra)] size_[static_caststd::size_t(rb)];--components_;return true;}bool connected(int a, int b) { return find(a) find(b); }int componentSize(int x) {return size_[static_caststd::size_t(find(x))];}int components() const { return components_; }private:static std::size_t checkedSize(int n) {if (n 0) {throw std::invalid_argument(negative size);}return static_caststd::size_t(n);}std::vectorint parent_;std::vectorint size_;int components_;};class DsuByRank {public:explicit DsuByRank(int n): parent_(checkedSize(n)),rank_(checkedSize(n), 0),components_(n) {std::iota(parent_.begin(), parent_.end(), 0);}int find(int x) {if (parent_[static_caststd::size_t(x)] ! x) {parent_[static_caststd::size_t(x)] find(parent_[static_caststd::size_t(x)]);}return parent_[static_caststd::size_t(x)];}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)];}--components_;return true;}bool connected(int a, int b) { return find(a) find(b); }int components() const { return components_; }private:static std::size_t checkedSize(int n) {if (n 0) {throw std::invalid_argument(negative size);}return static_caststd::size_t(n);}std::vectorint parent_;std::vectorint rank_;int components_;};int main() {DsuBySize dsu(6);dsu.unite(0, 1);dsu.unite(2, 3);dsu.unite(1, 3);std::cout std::boolalpha dsu.connected(0, 2) \n // true dsu.connected(0, 4) \n // false dsu.components() \n // 3 dsu.componentSize(2) \n; // 4DsuByRank dsr(6);dsr.unite(0, 1);dsr.unite(2, 3);dsr.unite(1, 3);std::cout dsr.connected(0, 2) \n dsr.components() \n;return 0;}按标准语义推演:六个元素初始为六个分量。合并 0-1、2-3 后剩四个分量;合并 1-3 把两个二元集合并成四元集合,剩三个分量;connected(0, 2)为真,connected(0, 4)为假,componentSize(2)为 4。按秩版本对同一组操作得到相同的连通性结论。以上只按代码逻辑推导,未经编译运行核对。五、复杂度与适用场景实现合并策略查询优化最坏/均摊复杂度朴素随意挂无单次 O(n)仅按大小或按秩小树挂大树无单次 O(log n)仅路径压缩随意挂全路径压缩均摊 O(log n)两者结合小树挂大树全路径压缩均摊 O(α(n))反阿克曼函数 α(n) 增长极慢,对任何可想象的输入规模都小于 5,所以说「近似常数」是准确的,但不要据此写成「严格 O(1)」——它不是常数。并查集适合处理动态连通性:网络节点是否连通、图的连通分量计数、Kruskal 最小生成树、网格渗流、等式约束的传递闭包等。它不支持「删除」或「拆分集合」,遇到这类需求要换数据结构(例如可持久化并查集或离线倒序处理)。常见坑点一、初始化时忘记让每个节点指向自己❌std::vectorint parent(n);默认全为 0,所有节点都被当成根 0 的子节点。✅ 用std::iota(parent.begin(), parent.end(), 0)初始化,或循环写parent[i] i。二、按大小合并时比较了错误的量❌if (size_[a] size_[b]) swap(a, b);其中a、b是原始节点而非根。✅ 先a find(a); b find(b);,确认两者是根之后,再比较size_[a]与size_[b]。三、合并后仍从非根节点读size❌ 压缩或合并之后,用某个非根节点的size_[x]回答「集合大小」。✅ 先find(x)找到根,再读根上的计数;非根节点的计数没有意义。四、按秩合并时无条件增加秩❌ 每次合并都rank_[ra],秩很快膨胀,失去「高度上界」的含义。✅ 只在两棵树秩相等时给新根加一;秩不等时新根的秩保持不变。五、只用路径压缩却用递归实现❌ 合并顺序不利时树高可达 O(n),递归find导致栈溢出。✅ 同时使用按大小/秩合并;或者把find写成迭代式两趟压缩。六、路径压缩后仍假设父子编号有序❌ 依赖「父节点编号一定小于子节点」来遍历或剪枝。✅ 压缩会把节点直接挂到根,编号关系不再成立;需要有序信息时另行维护。七、多组测试数据之间忘记重置❌ 复用同一个并查集对象,上一组数据的连通关系残留,答案错误。✅ 每组数据重新构造,或提供reset(n)重新初始化parent、size/rank与分量计数。八、越界下标未检查❌ 节点编号从 1 开始,却用Dsu(n)构造,访问find(n)时越界,operator[]越界是 UB。✅ 统一编号体系:要么全部减一成 0 到n-1,要么构造n1个元素并只使用 1 到n。总结并查集的优化可以概括为两句话:合并时让「小树挂到大树」,查询时让「路径上的点直接连根」。前者控制树的形状,后者摊还查询代价;单独使用各有 O(log n) 的保证,合起来才有 O(α(n)) 的均摊复杂度。实现时盯住三处:初始化、只对根操作、以及多组数据之间的重置。把这三处写对,并查集几乎是常数级的连通性工具。优化作用复杂度无优化直接挂接最坏 O(n)按 size 合并小树挂大树O(log n)按 rank 合并控制树高O(log n)路径压缩查询时压平路径摊还接近常数两者结合形状与路径同时优化O(α(n))
