并查集必须初始化parent[i]=i且每次union前先find根，否则路径压缩和按秩合并失效；连通性判定唯一可靠方式是find(x)==find(y)。
为什么 find 里不写路径压缩就白搭
不做路径压缩的 find 只是普通递归找根，树高可能退化到 O(n)，多次查询后整体效率崩掉。真正起效的压缩必须在递归返回时把当前节点直接挂到根下——不是“找到根就返回”，而是“先让父节点指向根，再把自己指向根”。
常见错误是写成：return parent[x] = find(parent[x]) 却没保证 parent 数组初始化正确，或在非递归版本里漏掉中间节点更新。
- 必须用递归实现压缩（迭代版需额外栈或两遍扫描，易错）
-
parent初始值必须设为自身：parent[i] = i - 压缩只发生在
find调用中，union过程不负责压路径
C++ 中用 vector 实现带按秩合并的 union 怎么避免越界和重复合并
按秩合并（union by rank）本质是把矮树连到高树根上，控制树高不超过 O(log n)。但很多人只关注 rank 比较，却忽略两个细节：一是合并前必须先 find 各自根节点，否则可能把非根节点当根去连；二是合并后仅更新被挂载方的根的 rank，且仅在两树高度相等时才加一。
典型错误现象：union(2, 3) 后再 union(3, 4) 出现“伪连通”——因没对 3 先做 find，导致把 3 当作独立根连向 4，实际破坏了已有的连通关系。
立即学习“C++免费学习笔记（深入）”；
- 每次
union(a, b)必须先int ra = find(a), rb = find(b) - 若
ra == rb，直接返回，不操作rank或parent - 只在
rank[ra] == rank[rb]时，才对作为新根的一方执行rank[root]++
如何用 find 返回值快速判定两个点是否连通
连通性判定唯一可靠方式是比对 find(x) == find(y) 的结果，而不是看 parent[x] == parent[y]——后者在未压缩路径时完全不可靠，即使 x 和 y 已连通，它们的父节点也可能不同。
性能上，只要 find 带压缩，两次调用开销接近常数，不必缓存结果。但要注意：如果在一次逻辑中反复查同一对点，可临时存根节点减少冗余调用。
- 禁止用
parent[x] == parent[y]判连通 - 不要为了“省一次
find”而提前保存parent值，它随时可能被后续find改写 - 多线程环境下必须加锁或改用原子操作，
find非纯函数
完整可运行的 C++ 源码里最容易漏掉的三处初始化
一份看似正确的并查集代码跑测试失败，80% 是初始化遗漏。最常被跳过的不是算法逻辑，而是数据结构本身的起点状态。
-
parent数组没初始化：声明vector<int> parent(n)</int>后必须显式循环赋值parent[i] = i，否则是随机值 -
rank数组全为 0 是对的，但若误用vector<int> rank(n, -1)</int>或忘记声明，会导致合并逻辑错乱 - 输入点编号从 1 开始？那
parent大小得是n+1，且初始化范围是[1, n]，否则访问parent[1]越界
路径压缩和按秩合并本身并不复杂，难的是每一步都守住前提条件：根必须是自环、所有操作前先找根、连通性只认 find 结果。少一个，就不是“快速判定”，只是看起来像。
