路径压缩正确写法是递归调用后立即更新当前节点父指针，即parent[x] = find(parent[x])，确保沿途节点逐级挂到根下而不破坏语义；必须修改原数组且返回根节点，迭代实现需额外存储路径并反向更新。
路径压缩怎么写才不破坏并查集的语义正确性
路径压缩的核心不是“让所有节点直接连到根”，而是“在查找过程中把沿途节点逐级挂到根下”，否则会干扰后续合并操作的逻辑判断。常见错误是把 find 写成无副作用的纯函数，或者在压缩时跳过父节点更新导致链断裂。
正确做法是：递归调用后立即更新当前节点的 parent，且只在返回前赋值。这样既保证了路径上每个节点最终指向根，又不影响当前查找过程中的中间状态。
- 必须用递归或显式栈实现，不能用简单循环+重定向——否则无法回溯更新父指针
-
find函数必须返回根节点，且修改原数组，这是路径压缩生效的前提 - 若使用迭代写法，需额外存储路径节点（如
std::vector<int></int>），再反向更新，否则会丢掉中间父节点信息
带路径压缩的 union 操作为什么不能只靠 find 判断是否连通
单纯比较 find(a) == find(b) 能判断连通性，但合并时若不做秩/大小优化，高频操作下树高仍可能退化。路径压缩单独存在时，union 的时间复杂度理论上限仍是 O(log n)，只有配合按秩合并（union by rank）或按大小合并（union by size）才能逼近反阿克曼函数 α(n)。
典型误判是认为“有路径压缩就不用管合并策略”，结果在大量 union 操作后，单次 find 仍可能触发长链遍历（尤其在反复 union 同一集合时）。
立即学习“C++免费学习笔记（深入）”；
- 路径压缩解决的是“查得快”，不解决“并得稳”；合并策略决定树的初始结构质量
- 按秩合并中，
rank是上界估计值，不等于真实高度（因路径压缩会改变高度），所以只用于指导谁当父节点 - 若用按大小合并，需维护
size数组，且每次union后只更新根节点的size，子节点的size值无效、不可读
初始化和边界场景下容易被忽略的三个细节
实际编码中，90% 的运行时错误来自初始化不当或边界未覆盖，而非算法逻辑本身。比如负索引、越界访问、未初始化的 parent 数组、0-based 和 1-based 混用等。
- 数组大小必须严格为
n + 1（若节点编号从 1 到 n），且parent[i] = i初始化必须覆盖全部有效索引，漏掉一个就会在find中触发未定义行为 - 对不存在的节点（如编号 0 或 >n）做
find，应提前校验，否则可能访问野指针；C++ 中建议用assert(i > 0 && i 或抛异常 - 当
n == 0或n == 1时，union操作应安全跳过，避免对空数组取parent[0]等非法访问
C++ 完整可运行实现（含测试验证逻辑）
下面是一个最小可行实现，聚焦路径压缩 + 按秩合并，不含模板泛化或容器封装，便于调试和嵌入现有项目：
#include <iostream>
#include <vector>
#include <cassert>
struct UnionFind {
std::vector<int> parent;
std::vector<int> rank;
int n;
UnionFind(int size) : n(size), parent(size + 1), rank(size + 1, 0) {
for (int i = 1; i <= n; ++i) parent[i] = i;
}
int find(int x) {
assert(x > 0 && x <= n);
if (parent[x] != x) {
parent[x] = find(parent[x]); // 关键：先递归，再赋值
}
return parent[x];
}
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) {
parent[rx] = ry;
} else if (rank[rx] > rank[ry]) {
parent[ry] = rx;
} else {
parent[ry] = rx;
rank[rx]++;
}
}
bool connected(int x, int y) {
return find(x) == find(y);
}
};
// 验证：插入 1-5，合并 (1,2), (3,4), (2,4)，最后检查 1 和 5 是否不连通、1 和 4 是否连通
int main() {
UnionFind uf(5);
uf.unite(1, 2);
uf.unite(3, 4);
uf.unite(2, 4);
std::cout << uf.connected(1, 4) << " "; // 1
std::cout << uf.connected(1, 5) << "\n"; // 0
}
注意：这里 parent 和 rank 都从索引 1 开始使用，0 位置闲置。若需支持 0-based 节点，只需把构造函数里循环改成 for (int i = 0; i 并调整 <code>assert 条件——但千万别混用。
真正难调试的，往往不是算法主干，而是初始化范围、索引偏移、以及 find 中那行看似简单的 parent[x] = find(parent[x])——它必须出现在 return 之前，且不能被任何条件提前截断。
