路径压缩比按秩合并更关键，因其将查找路径上所有节点直接指向根，使find接近O(α(n))；单独使用已足够应对大多数场景，而按秩合并仅为理论最优组合的可选补充。
为什么路径压缩比只用按秩合并更关键
单纯按秩合并（union by rank）能让树高保持在 O(log n)，但路径压缩能直接把查找路径上的所有节点指向根，使后续 find 接近 O(α(n))——实际中几乎常数时间。不加路径压缩时，反复 union 后再查深度大的节点，find 可能退化成 O(n)；加了之后，哪怕初始结构歪斜，几次 find 就压平了。
实操建议：
- 路径压缩必须在
find内部递归或迭代完成，不能只改直接父节点 - 不要在
union里手动调用find后再改父指针——这会漏压中间层 - 按秩合并可选，但和路径压缩组合后理论复杂度最优；单独用路径压缩已足够应对绝大多数场景
C++中用vector实现并查集的内存与索引陷阱
std::vector<int> 是最常用底层容器，但容易踩两个坑：一是下标越界（比如用节点编号 1~n 却以 0 为起点初始化），二是误把 parent[i] 当作“当前集合代表”，而它只是父节点——真正代表要靠 find(i) 得到。
常见错误现象：union(1,2); union(2,3); find(1) != find(3) ——多半是没在 find 中更新路径，或初始化时 parent[0] 被忽略导致索引错位。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 若输入节点编号从 1 开始，
parent大小设为n+1，只使用索引 1..n - 初始化写成
for (int i = 1; i ，别用 <code>resize(n), then i=0..n-1混淆语义 - 避免用
parent[i] == i判断是否为根——路径压缩后可能暂时不等，必须用find(i) == i
递归 vs 迭代实现 find 的实际取舍
递归写法简洁：return parent[x] == x ? x : parent[x] = find(parent[x]);，但深树可能栈溢出（尤其未优化递归、n > 1e6 时）；迭代写法稍长但可控，且方便在压缩前先遍历路径。
性能影响：现代编译器对尾递归优化有限，g++ -O2 下递归版在 n=1e5 级别仍安全，但生产环境建议迭代。
实操建议（迭代版核心逻辑）：
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;
}
- 第一遍找根，第二遍回压——两趟遍历比边找边压（如用栈存路径）更省内存
- 不要省略第二遍：只改
x的父节点，不改其子节点，路径压缩不彻底 - 如果需返回原始
x的旧父节点（极少见），得额外保存，否则直接覆盖无副作用
判断连通性时，别在 union 前重复 find
写 if (find(a) != find(b)) union(a, b); 没问题，但有人为了“保险”写成 if (find(a) != find(b)) { int ra = find(a), rb = find(b); union_by_rank(ra, rb); }——这会导致 a 和 b 各被压一次路径，ra/rb 却未必是最终根（因 union_by_rank 可能改父节点），后续再 find 又得重压。
更糟的是，在 union 内部又调一遍 find，形成冗余查找。
实操建议：
-
union函数应接收原始节点 a/b，内部自行find一次并缓存结果 - 若用了按秩合并，
union应返回 bool 表示是否真正合并（用于计数连通分量变化） - 连通性判定统一走
find(u) == find(v)，别依赖parent[u] == parent[v]——压缩后它们可能不同但同根
路径压缩的威力不在第一次，而在后续所有查找；最容易被忽略的是：它让“连通性查询”的成本变得几乎与操作历史无关，但前提是每次 find 都真实执行了压缩，而不是靠侥幸或半截实现。
