find必须递归或迭代+临时变量，因朴素迭代无法回溯更新父指针；路径压缩需在查找根时将路径节点直连根；仅路径压缩均摊O(log n)，加按秩/大小合并才达O(α(n))。
为什么 find 必须写成递归或带临时变量的迭代？
路径压缩的核心是“在查找根节点的同时，把沿途所有节点直接挂到根下”。如果用朴素迭代（只用一个指针一路跳），你无法在回溯时更新父指针——因为没保存路径。所以常见错误是写成：
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
这完全没有压缩。正确做法要么递归（自然回溯）：
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
要么迭代+记录路径：
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
- 递归写法简洁，但深度大时有栈溢出风险（一般 10⁵ 节点内安全）
- 迭代写法稍长，但可控、无栈开销，适合嵌入式或超大集合
- 别在
find里漏掉return parent[x]—— 压缩后必须返回更新后的根，否则union会连错
union 操作要不要按秩合并？只靠路径压缩够不够？
只做路径压缩，find 均摊复杂度是 O(log n)，加上按秩合并（或按大小合并）才能降到 O(α(n))，即反阿克曼函数，实际可视为常数。不加的话，极端构造数据（如链状合并）会让树退化，多次 find 变慢。
立即学习“C++免费学习笔记（深入）”；
推荐按大小合并（更直观，无需额外秩数组）：
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
-
size数组初始化为 1，每个节点自成集合时大小为 1 - 务必先
find再比较大小，否则合并的是非根节点，破坏结构 - 如果只关心连通性判定（不查集合大小），可以省略
size，但性能上限会降低
初始化和边界：数组大小、索引从 0 还是 1 开始？
并查集本质是基于数组的森林，下标即节点 ID。C++ 中最易错的是越界和索引偏移：
- 若节点编号是 1~n，就申请
parent[1 + n]，用parent[1]到parent[n]，别用vector<int>(n)</int>然后访问[i]（会越界） - 统一初始化：
iota(parent.begin(), parent.end(), 0)或循环设parent[i] = i - 如果输入含 0 节点，且你用了
vector<int> parent(n)</int>，那parent[0]合法；但如果节点是 1~n，用vector<int> parent(n + 1)</int>更安全 - 别在
unite前忘了判空或判范围——比如读入边时没检查u,v是否 ≤ n
怎么验证路径压缩真的生效了？
光看结果正确不够，要确认树高是否被压平。简单办法：在 find 返回前加一句打印（调试时）：
// 调试用，正式提交删掉
if (parent[x] != x && parent[parent[x]] != parent[x])
cout << "before compress: " << x << " -> " << parent[x] << "\n";
或者统计每次 find 的跳转次数：
int find(int x) {
int steps = 0;
while (parent[x] != x) {
x = parent[x];
steps++;
}
// 此时 x 是根，再走一遍压缩...
return x;
}
- 初始建树后，第一次
find可能跳 5–10 步；压缩后再次find同一节点，应稳定为 1 步 - 如果多次运行后仍频繁跳 2 步以上，说明
find没真正更新parent[x]，大概率是漏了赋值或用了旧值 - 线上环境禁用任何输出，验证靠单元测试：对固定输入，断言
find(x)返回值一致且parent数组中非根节点的父节点是否全为根
路径压缩不是“做了就完事”，它和 find 的实现细节强耦合；按秩/大小合并也不是锦上添花，而是把理论复杂度拉进实用区的关键一环。最容易忽略的，是初始化时数组长度与节点编号范围的错位——一个 off-by-one 就让整个结构静默失效。
