并查集必须同时实现路径压缩和按秩合并才能保证均摊O(α(n))；find需更新父指针，union需用rank比较而非值大小，初始化不可遗漏rank数组，离散化或哈希映射可处理非连续编号。
怎么写一个靠谱的 union 和 find
并查集不是靠“教程”堆出来的，是靠两个函数能不能扛住路径压缩和按秩合并的双重压力。手写时最容易出问题的是 find 没做路径压缩，或者 union 没比较秩（rank）直接乱连，导致树退化成链表，find 从 O(α(n)) 变成 O(n)。
实操建议：
-
find必须递归或迭代实现路径压缩：找到根后，把当前节点父指针直接指向根，别只返回根而不改结构 -
union别用值大小比较，用rank数组（或size，但得统一）决定谁当爹；rank相等时才给一方rank++ - 初始化时，每个
parent[i] = i，rank[i] = 0，别漏掉rank数组初始化 - 如果用
vector<int></int>存parent和rank，下标从 0 开始，别拿输入节点编号直接当索引——比如节点编号是 1~n，就开vector<int>(n+1)</int>
为什么 std::set 或 std::unordered_set 不能替代并查集
因为它们不维护集合间的连通关系。你往 std::set 里插一堆数，它只管去重和排序；哪怕两个集合元素完全一样，你也看不出它们是否该被“合并”。并查集的核心是动态维护等价类，而标准容器没提供 merge、connected 这类语义操作。
常见错误现象：
立即学习“C++免费学习笔记（深入）”；
- 试图用多个
std::set手动合并——每次insert大量元素，时间复杂度飙升，且无法快速回答“a 和 b 是否同属一集” - 用
std::map<int int></int>存 parent 但忘了写find压缩，查几次就栈溢出或超时 - 误以为
std::disjoint_set是标准库组件——C++23 还没进，别搜了，没有
路径压缩 + 按秩合并，哪个能省？
都不能省。单独用路径压缩，最坏情况 union 会拉高树高；单独用按秩合并，find 仍是 O(log n)。两者合体才能保证单次操作均摊 O(α(n))，α 是反阿克曼函数，对所有实际输入都 ≤ 4。
实操注意点：
- 按秩合并中的“秩”不是真实树高，只是上界估计，所以可以安全地只在两树秩相等时才
rank[root]++ - 路径压缩后，
rank值会失真，但这没关系——它只用于union决策，不参与find计算 - 如果图是静态的、只查询不修改，考虑用 DFS/BFS 求连通分量更直白；并查集的价值在“边加边查”的在线场景
边界情况：节点编号不连续 or 有负数怎么办
并查集底层是数组索引映射，不支持负数或稀疏编号。硬塞会越界或浪费内存。
解决办法很简单：
- 离散化：把所有出现过的节点值扔进
vector，排序去重，用lower_bound映射到 0~n-1 - 用
unordered_map<int int></int>代替vector存parent，但要注意：find里每次访问都要查哈希表，常数变大；而且你得自己处理未注册节点——第一次find(-5)时，得先parent[-5] = -5 - 别用
map（红黑树），查找慢还容易写错默认构造逻辑
离散化比哈希映射更稳，尤其数据量不大时；真要支持任意整数且动态极强，哈希方案就得配好初始化逻辑，否则第一次 find 就崩。
