c++实现并查集最稳妥的方式是用vector存储parent和rank数组，下标为节点编号，值为父节点下标或秩；需先find找根再合并，配合路径压缩与按秩合并才能保证o(α(n))效率。
为什么直接用 vector 存 parent 数组比指针/动态分配更稳妥
很多初学者会为每个节点 new 一个结构体，或者用 vector<node></node>，结果在合并时搞乱指针、忘记释放、或触发浅拷贝问题。C++ 实现并查集最稳的起点是 vector<int></int> 存根索引——下标即节点编号（0-based 或 1-based 一致即可），值为父节点下标。
这样做既避免内存管理开销，又天然支持随机访问，路径压缩时循环改父指针毫无压力。按秩合并用的 rank 数组也同理，vector<int></int> 足够。
- 别用
map<int int></int>模拟 parent：稀疏节点看似灵活，但find()平均变慢，且破坏了“连续编号→O(1)访问”的前提 - 如果节点编号不连续（比如 ID 是大整数），先离散化再映射到 0~n-1，而不是硬套 map
-
vector初始化大小必须 ≥ 最大可能节点数；若运行中动态加点，需预留或用reserve()减少重分配
find() 里递归 vs 迭代实现路径压缩的区别
递归写法简洁，但深树可能栈溢出（比如 10⁵ 节点链状结构）；迭代虽多几行，但安全可控，且更容易看出压缩逻辑：一路向上找根，再倒回来统一设父为根。
关键不是“压不压缩”，而是“是否所有经过节点都直连根”。有些代码只改了当前节点的父，漏掉中间层，那就没真正压缩。
- 错误示范：
parent[x] = find(parent[x]); return parent[x];—— 看似递归压缩，但 C++ 中未加记忆化时可能重复调用，且部分编译器优化后行为不可靠 - 推荐迭代：
int root = x; while (root != parent[root]) root = parent[root]; while (x != root) { int next = parent[x]; parent[x] = root; x = next; } - 别在
find()里修改rank：rank只在unionSet()中更新，且只更新根节点的值
unionSet() 中按秩合并的“秩”到底该存什么
这里的“秩”不是真实树高，而是**上界估计值**，用于控制合并方向。它只在两子树根秩相等时才对新根 +1，其余情况不更新。误把它当实际高度去维护（比如每次合并后重算），反而破坏 O(α(n)) 复杂度保证。
常见误区是把 rank 和节点数量（size）混用。按大小合并（union-by-size）也可行，但和按秩合并（union-by-rank）是两种独立优化策略，不要在一个实现里同时改 rank 和 size 又不区分用途。
- 按秩合并：初始化
rank[i] = 0；合并时，让rank小的根挂到rank大的根下；相等时任选其一为根，并对其rank++ - 按大小合并：初始化
size[i] = 1；合并时，小 size 树挂到大 size 树下，后者size += former_size - 二者不能混用：比如用
rank数组却按 size 比较，会导致压缩失效或复杂度退化
合并操作前忘了 find() 查根，导致逻辑错误
这是最隐蔽也最高频的 bug：直接对两个原始输入节点 x 和 y 做 unionSet(x, y)，但没先调 find(x) 和 find(y) 找各自所在集合的根。结果可能把两个本就同属一棵树的节点再次合并，或者挂错层级，破坏树结构。
正确流程永远是：先 find 根，再比较是否同根（是则跳过），否则按秩/大小合并两根。
- 错误写法：
if (rank[x] —— 此时 <code>x和y很可能不是根，rank[x]完全无意义 - 正确骨架：
int rx = find(x), ry = find(y); if (rx == ry) return; if (rank[rx] rank[ry]) parent[ry] = rx; else { parent[ry] = rx; rank[rx]++; } - 调试技巧：打印每次
unionSet前后的find(x)和find(y)，确认它们是否真为根；跑小样例（如 4 个点连成环）立刻暴露问题
unionSet 都要基于根节点操作——这个前提一旦松动，所有优化都白搭。C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
