路径压缩需两次遍历：第一次递归到底找到根，第二次回溯时统一将路径上所有节点父指针指向根；按秩合并用rank（树高）而非size更稳定，仅当两树rank相等时新根rank+1；初始化须显式设parent[i]=i、数组大小留足、操作前校验索引合法。
为什么 find 必须两次遍历才能做路径压缩
路径压缩不是“边找边改”就能生效的——第一次递归到底找到根节点后，第二次回溯时才把沿途每个节点的 parent 直接连到根。如果只用一次迭代或单次赋值（比如写成 parent[x] = find(parent[x]) 但没等递归返回），压缩会漏掉中间层。
常见错误是试图用循环替代递归，却忘了在更新父节点前先拿到最终根节点：
int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]]; // 错！这叫「隔代压缩」，不彻底
x = parent[x];
}
return x;
}
正确做法是递归获取根，再统一上提：
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]); // 先递归到底，再赋值压缩
}
return parent[x];
}
union 操作里按秩合并（rank）比单纯看大小更稳
用子树高度（rank）控制合并方向，能保证最坏树高始终 ≤ log n；而按 size 合并虽也有效，但在频繁删除/重建场景下 rank 更稳定，且避免了维护额外 size 数组的开销。
关键点：
-
rank[i]初始为 0，仅当两子树rank相等时，新根的rank才 +1 - 合并时永远把
rank小的树挂到rank大的树下；相等则任选其一为根，并更新其rank - 不要在
find里修改rank——它只在union中被动更新
初始化和边界检查容易忽略的三个细节
实际部署时出错常不在算法逻辑，而在初始化疏漏：
-
parent数组必须显式初始化为i，不能依赖全局变量零值（尤其在多次复用结构体时） - 若节点编号从 1 开始（如输入给的是 1~n），数组大小要开到
n+1，否则parent[n]越界 - 调用
union(x, y)前，应确保x和y都在合法范围内，否则find访问非法索引直接崩溃
建议封装成类后，在构造函数中强制校验 n > 0 并完成初始化：
DSU(int n) : parent(n), rank(n, 0) {
for (int i = 0; i
<h3>连通性判定别直接比节点 ID，要先 <code>find</code>
</h3>
<p>用户最容易犯的错：写 <code>if (a == b)</code> 或 <code>if (parent[a] == parent[b])</code> 来判断连通——这两者都错。前者只判是否同一节点，后者没经过路径压缩，父节点可能还不是根。</p>
<p>唯一可靠方式是：</p>
<pre class="brush:php;toolbar:false;">bool connected(int a, int b) {
return find(a) == find(b);
}
注意：即使刚做完 union(a, b)，也不能跳过 find 直接比较，因为 a 和 b 的父节点可能尚未压缩到根（尤其在未触发递归的浅层调用中）。
性能上，connected 本质就是两次 find，均摊时间接近 O(α(n))，不必担心额外开销。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
