路径压缩与按秩合并必须配合使用：仅路径压缩无法控制树高增长，仅按秩合并无法加速查找；二者结合才能使find和union均摊复杂度达O(α(n))。
为什么路径压缩后还要配合按秩合并
单纯做路径压缩，find 操作均摊接近 O(1)，但树高可能在某些操作序列下意外变高；反过来，只做按秩合并（union by rank）能控制树高 ≤ log n，但 find 仍要走完整路径。两者合用才能保证单次 find 和 union 均摊时间复杂度稳定在近乎常数级（阿克曼函数反函数 α(n)）。实际编码中漏掉按秩合并，长期运行后某些连通块的树退化成链表，find 会突然变慢——尤其在动态加边+高频查询的图处理场景里。
C++ 中路径压缩的两种写法差异在哪
常见错误是用迭代压缩却没更新中间节点的父指针，或递归压缩时忽略返回值赋值。正确写法必须确保「所有被访问节点直接指向根」：
// ✅ 推荐：递归写法，简洁且天然保证逐层回溯更新
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
// ⚠️ 迭代写法需两遍遍历（先找根，再重连）
int find(int x) {
int root = x;
while (root != parent[root]) root = parent[root];
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
递归版更安全，但极端深度下有栈溢出风险（n > 1e6 且初始为链状时）；迭代版无栈风险，但容易漏掉第二轮赋值，导致压缩失效。
按秩合并中的 rank 是高度还是大小
这里 rank 表示「该树近似高度上界」，不是节点数量。它只在合并时用于比较，不参与路径压缩后的更新。误把它当成子树大小（size）会导致合并策略失衡：
立即学习“C++免费学习笔记（深入）”；
- 用
rank合并：小树根挂到大树根下，rank仅在两树高度相等时 +1 - 若误用
size实现 union by size，则应另建sz数组，且合并逻辑变为「小 size 树挂到大 size 树下」 - 两者效果接近，但
rank更省空间（16-bit short 足够），size在需要统计连通分量大小时更直接
混用 rank 和 size 变量名但逻辑错配，是调试时最难发现的隐性 bug。
初始化和边界访问容易踩哪些坑
典型问题集中在数组越界、未初始化、以及对负索引或 0-based/1-based 混淆：
-
parent和rank数组必须从 0 到 n−1 全部初始化：parent[i] = i，漏初始化某个索引会导致find(-1)或野指针 - 输入节点编号若为 1~n，但代码按 0~n−1 分配数组，却用原始编号直接访问
parent[x]→ 越界 - 合并前未检查
x和y是否已合法（比如读入错误导致 x = -1），find(-1)访问parent[-1]触发未定义行为 - 多组测试用例复用同一并查集对象时，忘记重置
parent和rank数组
最稳妥的做法是在构造函数里用 std::vector 动态分配，并在每次使用前显式调用 init(n) 方法重置，而不是依赖全局静态数组。
