路径压缩应在find中递归实现：先递归找到根，再将当前节点父指针指向根，确保沿途所有节点直连根节点而不改变连通性；union需基于find后的根节点操作，并配合按秩或按大小合并以保证均摊O(α(n))复杂度。
路径压缩怎么写在 find 里才不破坏并查集语义
路径压缩的核心是让查找过程中沿途所有节点直接指向根，但必须确保不改变连通性判断逻辑。常见错误是只改了当前节点的 parent，却没递归更新中间节点——这会导致后续查找仍要遍历旧路径。
正确做法是用递归（或迭代+栈）先找到根，再回溯统一挂载。推荐递归写法，简洁且不易漏节点：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 关键：先递归找根，再赋值
}
return parent[x];
}
-
parent[x] = find(parent[x])这一行必须在return前执行，且不能拆成两步（比如先int root = find(...)再赋值），否则压缩失效 - 如果用迭代，需额外记录路径上所有节点，最后批量设父节点，代码更长、易错
- 注意：
find不应修改rank或size，这些只在union中更新
union 操作要不要按秩合并？不加会怎样
路径压缩本身不保证树高，单独使用时最坏情况仍是 O(n) 查找（虽然均摊接近常数）。加上按秩合并（或按大小合并）才能确保单次操作均摊 O(α(n))。
按秩合并更省空间（只需一个整型数组），按大小合并语义更直观。两者选其一即可，别两个都维护：
立即学习“C++免费学习笔记（深入）”；
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) {
parent[x] = y;
} else if (rank[x] > rank[y]) {
parent[y] = x;
} else {
parent[y] = x;
rank[x]++;
}
}
- 必须对
find后的根节点比较和连接，否则可能把非根节点当根处理 - 如果用大小合并，把
rank换成size数组，合并时把小树挂到大树下，size[root] += size[other] - 不加按秩/按大小合并，单纯路径压缩在极端数据下（如链状合并）仍可能退化，实测小数据看不出差别，大数据容易卡
初始化和内存布局要注意什么
并查集本质是数组模拟的森林，parent[i] 存的是节点 i 的父节点索引。常见坑是索引越界或初始化错位。
- 节点编号建议从
0开始，parent数组大小为n，初始化：for (int i = 0; i - 如果节点编号不连续（比如来自哈希 ID），得先离散化映射到
[0, n)范围，否则数组开太大或访问非法地址 -
rank或size数组也必须和parent同大小，且只对根节点有意义；非根节点的rank值无意义，别拿它做判断 - C++ 中推荐用
std::vector<int>而不是裸指针，避免手动new/delete和越界风险
怎么验证路径压缩真的生效了
不能只看最终结果是否连通，得检查中间状态。最直接的方法是打印某次 find 后的 parent 数组变化。
例如初始 0-1-2-3（链状），调用 find(3) 后，理想状态是 parent[3]=0、parent[2]=0、parent[1]=0，而不是只有 parent[3]=0。
- 加个调试函数：
void dump() { for (int i = 0; i - 注意：多次
find后，同一节点的parent可能被反复更新，只要最终指向根就正确 - 别依赖
find返回值判断压缩效果——它总返回根，得看parent数组内容
路径压缩的“简单”是假象，真正容易出问题的是初始化边界、find 递归顺序、以及和按秩合并的配合时机。这几个点没踩准，跑得慢还是小事，连通性出错才是真麻烦。
