路径压缩必须在find中递归实现，因递归回退时才能将路径上各节点父指针直接指向根；仅return find(parent[x])不更新parent[x]，导致压缩失效。
路径压缩必须在 find 里完成，否则每次查询都可能退化成 O(n)；按秩合并不是必须的，但不加它，均摊性能上限会从 O(α(n)) 掉到 O(log n)，实际数据大时慢 2–3 倍。
为什么 find 必须递归写，且不能只写 return find(parent[x])
路径压缩的本质是：查到根之后，把整条路径上所有节点的 parent 直接设为根。递归天然提供“先到底、再回退”的时机，而 return find(parent[x]) 只做了查找，没改当前节点的 parent，压缩就丢了。
- 错误写法：
return find(parent[x])—— 返回了根，但parent[x]没变，下次查x还得走老路 - 正确写法：
parent[x] = find(parent[x]); return parent[x];—— 先递归拿到根，再把x挂过去 - C++ 不保证赋值右操作数一定先求值，
parent[x] = find(parent[x])在复杂上下文中可能读到旧值，建议拆成两步：int root = find(parent[x]); parent[x] = root; return root; - 递归终点必须是
parent[x] == x，不能只靠!=判断，否则未初始化或越界时容易死循环
union 里不检查连通性会出什么问题
重复合并同一集合，会让 rank 或 size 统计失真，长期影响树结构质量。尤其在 Kruskal、社交图等含重边场景下，漏判直接导致性能滑坡。
- 必须先
int ra = find(a), rb = find(b);，再判断if (ra == rb) return; - 别用
parent[a] == parent[b]替代 —— 那俩可能都还不是根，比较结果完全不可靠 - 按大小合并时，合并后要更新：
size[ra] += size[rb];；按秩合并时，仅当rank[ra] == rank[rb]才执行rank[ra]++ - 合并只动根节点的
parent和rank/size，中间节点的更新全靠后续find触发
数组大小和索引偏移怎么设才不越界
节点编号从 1 开始却用 vector<int>(n)</int> 是最常见越界源。parent 数组下标必须能覆盖所有输入节点 ID，否则 find(100) 直接踩内存。
- 若输入节点是 1~n，开
vector<int> parent(n + 1)</int>，然后for (int i = 1; i - 别依赖全局变量零值初始化 —— 多次复用对象时，
parent[0]可能残留上次数据，造成虚假连通 - 用
std::iota(parent.begin(), parent.end(), 0)初始化更安全，语义也更清晰 - 调用
find(x)前，应校验x >= 0 && x ，尤其处理文件输入或网络数据时
迭代版 find 怎么写才不漏压节点
递归在 n ≤ 1e5 时基本安全，但超大图或嵌入式环境需迭代。关键不是“省栈”，而是确保两遍遍历：第一遍找根，第二遍从原始 x 出发，逐个把路径上节点的 parent 设为根。
- 第一遍不能只记
root就完事，必须完整跳到根，确认无误 - 第二遍必须用临时变量存
next = parent[x]，再改parent[x] = root，否则x更新后找不到下一个 - 漏掉第二遍，或只改了
x的父节点，中间层节点仍指向旧父节点，压缩就不彻底 - 别在迭代里尝试“边走边压”（比如
parent[x] = parent[parent[x]]），那是隔代压缩，不收敛也不稳定
最容易被忽略的是：路径压缩不是一次性的，它只作用于当前查询路径；判定连通性前，find(a) 和 find(b) 必须各自执行完毕，否则其中一个的路径还是弯的，下次查它照样慢。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
