c++中并查集最稳实现是用两个std::vector：parent存父节点，rank或size存秩/大小；必须初始化parent[i]=i，find须迭代路径压缩至根，union按秩或大小合并且函数名避免与stl冲突。
用 std::vector 实现并查集，别手写链表
并查集在 C++ 里最常用、最稳的实现方式就是两个 std::vector：一个存父节点（parent），一个存秩或大小（rank 或 size）。手写指针链表不仅没优势，还容易内存泄漏、破坏缓存局部性。
常见错误是初始化时漏掉 parent[i] = i，导致后续 find 直接越界或死循环；或者把 rank 初始化成全 0 后，误以为“高度为 0”等于“未访问”，其实它只是初始合并优先级依据。
-
parent大小必须是n，索引从0到n-1，构造时逐个设为自身 - 按秩合并（
union by rank）比按大小合并（union by size）稍快一点，但差别极小；选哪个取决于你后续要不要查集合元素数——要就用size，否则用rank - 路径压缩只在
find里做，别在union里重复调用find两次再压缩，那会多一次函数调用开销
find 必须带路径压缩，且不能写成递归形式
递归版 find 看起来简洁，但在 n > 1e5 时极易爆栈，尤其 Windows 下默认栈只有 1MB。迭代写法更安全，也更容易被编译器内联。
典型错误是压缩时只改了一层父节点（比如 parent[x] = parent[parent[x]]），这叫“半压缩”，无法摊还到 O(α(n))；真正压缩要一路找到根，再倒回来赋值。
立即学习“C++免费学习笔记（深入）”；
- 正确做法：先用循环找到根
root，再用第二遍循环把路径上所有点的parent设为root - 别在
find里修改rank或size——它们只在union时更新 - 如果用
const引用传入parent，编译直接报错；find必须能修改数据结构
union 函数名别叫 merge 或 join，小心和 STL 冲突
C++ 标准库里有 std::merge、std::set_union，自定义函数起名太泛容易引发 ADL（参数依赖查找）问题，尤其当参数类型是 int 这种基础类型时，编译器可能意外拉进 std 命名空间里的同名函数。
另一个坑是合并逻辑写反：把小树挂到大树下是对的，但有人会把 rank[a] 判定后，错误地把 <code>a 的父设成 b，却忘了此时 a 才是深度小的那个，该被挂过去——逻辑和代码要严格对齐。
- 推荐函数名：
unite（LeetCode 官方题解常用）、merge_sets（清晰无歧义） - 统一用
int find(int x)返回根，不要返回引用或指针；避免后续误改中间节点 - 如果输入坐标是 1-indexed（比如题目给的是 1~n），记得在调用
unite(a-1, b-1)前减一，别只在初始化里处理
离线批量合并？别急着优化，先确认是否真需要
有人看到“高效”就去搞分治并查集（DSU on tree）或可撤销并查集（rollback DSU），但普通 O(m α(n)) 已经足够应对 2e5 数据量。99% 的 OJ 题和业务场景根本用不到那些变体。
真正值得提前考虑的是：是否要支持删除操作？是否要维护集合内最大/最小值？这些需求一旦出现，基础并查集就不再适用，得换 std::set + 启发式合并，或者上 link-cut tree——但那是另一回事了。
- 标准并查集不支持删边；所谓“撤销”本质是记录操作栈，空间翻倍，且只适用于离线+固定顺序
- 如果要频繁查询集合大小，用
size数组比每次遍历统计快得多，但要注意 union 后只更新根的size，别漏加 - 多线程环境？别自己加锁——标准并查集不是线程安全的；真需要并发，用
tbb::concurrent_unordered_set配合外部同步，而不是改 DSU 内部
路径压缩和按秩合并的组合已经把均摊复杂度压到极致，再多花哨操作，大概率是在解决一个不存在的问题。
