路径压缩比按秩合并更关键，因其直接将查找复杂度从o(log n)优化至o(α(n))，而按秩合并仅控制树高上限；实测中无路径压缩易退化为链表，加入后两次find即可基本压平。
为什么路径压缩比只用按秩合并更关键
路径压缩直接改变树的结构，让查找操作从 O(log n) 趋近于 O(α(n))（反阿克曼函数），而按秩合并只是控制树高上限。实际测试中，find 调用频繁时，没路径压缩的并查集在 10⁵ 次操作后可能退化成链表，耗时飙升；加上路径压缩后，哪怕初始是链状，两次 find 就基本压平。
实操建议：
- 路径压缩必须写在
find内部，且要递归或迭代地把沿途所有节点父指针指向根——不能只改当前节点 - 不要在
unionSet里手动调用find后再改父节点却不压缩：这会漏掉中间层，下次find还得重走 - 按秩合并（
rank）可选，但和路径压缩组合时，rank不再严格等于树高，仅作启发式参考，别拿它做逻辑判断
递归版 find 的写法与栈溢出风险
递归写法最直观，但面对 10⁶ 级别的节点且初始为单链时，容易触发栈溢出（尤其 Windows 默认栈仅 1MB）。不是所有编译器都对尾递归优化，C++ 标准也不保证。
推荐写法（带压缩的递归）：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 关键：先递归到根，再把父设为根
}
return parent[x];
}
注意点：
- 必须是
parent[x] = find(parent[x])，不是return find(parent[x])—— 后者没压缩 - 若确定数据规模大（>10⁵）或嵌入式环境栈小，改用迭代版：用 vector 记录路径，再统一更新父节点
- g++ -O2 下部分简单递归会被优化，但别依赖；生产代码建议默认用迭代
unionSet 中要不要再调用 find？
要，而且必须调用两次——分别压缩两个输入节点的路径，再比较根。不这么做会导致：节点 a 和 b 明明已连通，但因路径未压，find(a) 和 find(b) 返回不同值，误判为不连通。
典型错误写法：
// ❌ 错误：没压缩就直接比 parent[a] 和 parent[b]
if (parent[a] != parent[b]) { ... }
正确流程：
- 先
int ra = find(a)，int rb = find(b)—— 此时 a、b 及其路径全被压缩 - 再判断
ra == rb，避免重复查找 - 合并时，把秩小的根挂到秩大的根下；相等时任意挂，但被挂方
rank+1
数组 vs vector：初始化与边界检查取舍
用 std::vector<int></int> 更安全，支持运行时大小、自动扩容；但若节点数 N 编译期已知（如题目给定 1e5），用 int parent[100001] 能省掉堆分配开销，且缓存局部性更好。
关键细节：
- 无论哪种，初始化必须是
parent[i] = i，不能靠零初始化——int数组默认为 0，会导致所有节点初始父节点都是 0，逻辑全崩 - 如果用了
vector，记得resize(n+1)并循环赋值，或用构造函数：vector<int> parent(n+1); for (int i = 0; i </int> - 下标习惯：题中节点常为 1~n，数组开 n+1，用
parent[1]到parent[n]，别越界访问parent[0]（除非你真需要）
find 都真实改变了至少一个节点的父指针。调试时如果发现连通性判断不准，优先检查 find 是否真的执行了赋值，而不是只读了值。C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
