单纯union易致树退化为链表，因无规则挂载使深度激增；按秩合并通过“矮树认高树当爹”控制树高，秩仅在两树秩相等时加1，且不与路径压缩冲突。

为什么单纯 union 会退化成链表

不加控制的 union 操作，每次把一个树根直接挂到另一个树根下，很容易让深度不断增长。比如按输入顺序合并 1-2、2-3、3-4…，最终得到一条深度为 n 的链，find 就从 O(α(n)) 退化成 O(n)。

按秩合并（union by rank）的核心是：**只允许矮树认高树当爹**——用“秩”（rank）近似表示树高，不是真实高度，但保证不会高估。秩只在两棵树秩相等时才需要 +1。

常见错误是把 rank 当成真实高度去维护，或者在路径压缩后还误用它做比较（其实按秩合并和路径压缩可共存，但 rank 不再等于高度，不影响正确性）。

怎么写带 rank 的 union 函数

union 操作必须先 find 两个元素的根，再比较秩，决定谁挂谁。关键点：只改根节点的 parent，不碰非根节点的 rank。

示例逻辑：

void union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rank[rx]  rank[ry]) {
        parent[ry] = rx;
    } else {
        parent[ry] = rx;
        rank[rx]++;  // 仅此处 +1，且只加一次
    }
}

注意：rank 数组初始全为 0；parent[i] = i 初始化；find 可独立实现路径压缩（不影响按秩合并逻辑）。

rank 和 size 合并策略能混用吗

不能直接混用。按秩合并（rank）靠的是树的“高度上界”，按大小合并（union by size）靠的是子树节点数。两者目标一致（控高），但维护方式和语义不同。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

如果你已经用了 size 数组，想换 rank，得重置数组并重新设计 union；反之亦然。混用会导致判断逻辑失效，比如拿 size[a] 却更新 <code>rank，完全失去约束意义。

实际选哪个？

• rank：内存稍省（int 值小，增长慢），理论分析常用
• size：更直观，某些场景（如需统计连通块大小）顺手复用

二者渐进复杂度一致，选一个坚持到底就行。

初始化和 find 需要配合做什么

find 可以（也推荐）加路径压缩，它和按秩合并不冲突——压缩只改中间节点的 parent，不影响根的 rank 值。但要注意：压缩后 rank 不再是真实高度，只是上界，这恰恰是设计本意。

初始化必须明确：

• parent[i] = i
• rank[i] = 0

漏设 rank 初始值（比如用未初始化内存）会导致不可预测的合并方向，极易链化。

按秩合并真正起效的前提，是所有合并都走你写的 union 函数，而不是绕过它直接改 parent。这点在封装成类时容易被忽略——确保 union 是唯一修改父关系的入口。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！