只需vector parent即可实现并查集，因根节点满足parent[i]==i，find通过递归更新parent[x]实现路径压缩，union需先判同根再合并，按秩合并与size优化非必需但可提升性能。
为什么直接用 vector<int></int> 存 parent 就够了
并查集核心就两件事：找根（find）和合并（union）。根节点的 parent[i] == i，其余节点指向父节点。不需要额外存 rank 或 size——除非你要按秩合并；路径压缩也不需要额外数组，改 parent 本身就行。
常见错误是搞混“当前节点”和“根节点”的返回值，比如在递归 find 里忘了把最终根赋给 parent[x]，导致压缩失效。
- 初始化：
parent[i] = i，每个点自成一集合 -
find(x)必须边查边改：parent[x] = find(parent[x])，不是先算再赋值 - 别用循环写路径压缩（容易漏改中间节点），递归最直白、不易错
find 函数怎么写才真正压缩路径
关键在递归返回时“顺手”把当前节点挂到根下。如果只写 return find(parent[x])，路径没变；必须显式更新 parent[x]。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // ← 这一行不能少，也不能写成 `return find(parent[x])`
}
return parent[x];
}
注意：这个写法天然避免重复压缩——如果 x 已经指向根，parent[x] == x，直接返回，不进 if。
立即学习“C++免费学习笔记（深入）”；
- 不要用 while 循环 + 二次遍历去压缩（性能差、易出错）
- 如果编译器栈深受限（极大数据量），可改用迭代版，但得手动维护路径节点列表
- 返回的是根节点编号，不是引用或指针，别试图通过返回值修改
parent
union 操作要不要检查是否同根、需不需要按秩合并
必须检查是否同根，否则会把树连成环（虽然不影响 find 正确性，但逻辑上不该合并同一集合）。
按秩合并（rank）不是必须的，但加了之后能保证单次 find 均摊接近 O(α(n))；只用路径压缩也能达到类似效果，但最坏单次 find 可能稍慢（实践中差别极小）。
- 基础版：先
find(a)和find(b)，相等就return；否则parent[ra] = rb - 加
rank：用vector<int> rank(n, 0)</int>，合并时让矮树根指向高树根；一样高时才rank[rb]++ - 加
size（用于优化某些场景如连通分量计数）：合并后更新size[rb] += size[ra]，但和路径压缩无直接关系
实际用的时候最容易忽略的三个细节
一是下标越界：初始化 parent 大小写成 n-1 或没考虑 0-based，find(0) 就崩；二是没重载 union（C++ 关键字），必须起名如 merge 或 unite；三是多次调用 find 时，误以为传入的是根——其实传任意节点都行，函数内部会自己找根。
- 测试小样例务必包含：初始化 → 合并两个点 → 再合并第三个点 → 查这三个点是否同根
- 别在
find里加cout调试——路径压缩会触发递归，输出顺序反直觉 - 如果要支持撤销（如可回退并查集），就不能用路径压缩，那是另一套设计
