unionfind 类应使用 vector parent 和 size，初始化 parent[i]=i；find 必须路径压缩，union 前先 find 根并按 size 合并，避免树高退化。
怎么写一个轻量可靠的 UnionFind 类
直接用数组 + 路径压缩 + 按秩合并，别手写链表或哈希映射——除非你真要处理字符串 ID。整型下标最稳，vector<int></int> 存父节点，初始化时 parent[i] = i。
常见错误是忘记在 find 里做路径压缩，导致后续查询退化成 O(n)；或者 union 时只改了一个方向的父节点，没比较秩（rank）或大小（size），合并后树高失控。
-
find必须递归或迭代地把沿途所有节点指向根，不能只返回根而不动路径 -
union前先find两个节点的根，相同就直接返回，避免自环 - 按秩合并用
vector<int> rank</int>，只在两棵树秩相等时才让一方当父，且该方秩 +1；按大小合并更直观，适合判断连通分量大小
class UnionFind {
vector<int> parent, size;
public:
UnionFind(int n) : parent(n), size(n, 1) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
};
为什么 find 用递归比循环更容易出错
不是不能用循环，而是新手常漏掉“更新父指针”这一步：循环找到根后，只返回根值，没把路径上每个节点的 parent 改成根。结果下次查还走老路，压缩失效。
递归写法天然带回溯赋值机会，只要写对 parent[x] = find(parent[x]) 这一行，压缩就自动完成。但要注意栈深度——10⁵ 节点+链式结构可能爆栈，这时得切迭代。
立即学习“C++免费学习笔记（深入）”；
- 递归版简洁安全，适用于 n ≤ 10⁴ 的常规场景
- 迭代版需额外存路径节点（如
vector<int></int>），再统一设父，代码略长但可控 - 别用 while(true) + break 模拟递归逻辑，容易漏更新中间节点
合并字符串 ID 时怎么避免 map 查找开销
如果输入是 "nodeA"、"nodeB" 这类字符串，硬套 map<string int></string> 映射会拖慢每次 find/unite，尤其高频调用时。
真正高效的做法是预处理：一次性读完所有 ID，用 unordered_map 映射到连续整数 0..n−1，之后全程用整数下标操作 UnionFind。别在 unite("a", "b") 里实时查 map。
- 预处理阶段允许 O(n log n)，运行期必须保持接近 O(α(n))
- 别用
map（红黑树），用unordered_map防止插入变慢 - 如果 ID 是带前缀的数字（如
"user_123"），可考虑提取数字部分直接转 int，跳过 map
UnionFind 在离线查询中怎么配合排序使用
比如「按边权从小到大加边，问第 k 次合并后有多少连通分量」——这种题不能边加边输出，得先把操作序列排好序，再逐个 unite，同时维护当前连通块数量或最大分量大小。
关键点在于：并查集本身不记录历史，所有依赖顺序的逻辑必须由外部控制。容易踩的坑是把查询混进合并循环里，结果查的是中间态而非题目要求的某个快照时刻。
- 把所有操作（合并/查询）按时间戳或条件排序，用索引驱动流程
- 查询类操作（如「此时连通块数」）只需统计
find(i) == i的个数，O(n) 一次就够了，别每步都扫 - 需要支持撤销？标准
UnionFind不行，得换可回滚版本（带栈的 union-by-size + 时间戳），那是另一回事了
路径压缩和按秩合并不是锦上添花，是保性能的底线。漏掉任何一个，面对 10⁵ 数据就可能从秒级变成秒超时。实际写的时候，先写对 find 的压缩，再补 unite 的秩/大小判断，比反过来调试成本低得多。
