unionfind 类核心是用 vector 维护 parent 和 size（或 rank），构造函数初始化 n 个独立集合；find 必须路径压缩，unionset 需先 find 再按大小/秩合并，避免直接操作非根节点。
UnionFind 类的基本结构怎么写
并查集核心是维护一组元素的连通性，C++ 中通常用 vector 存父节点索引，下标即元素编号。初始化时每个点自成集合，parent[i] = i。关键操作是 find（找根）和 unionSet（合并），注意函数名别和 C++ 关键字 union 冲突，推荐用 unionSet 或 merge。
常见错误是把 find 写成纯递归但没做路径压缩，或在 unionSet 里直接比较值而非根节点。
-
parent和rank（或size）都建议声明为private，避免外部误改 - 构造函数应接受
n并预分配parent大小，避免运行时扩容影响性能 - 不建议用
map存非连续编号——除非真有稀疏、动态插入需求，否则纯浪费
路径压缩为什么必须写在 find 里而不是 unionSet 里
路径压缩的本质是：每次 find(x) 时，把从 x 到根路径上所有节点的 parent 直接指向根。它只在查询时生效，且必须“边查边压”，不能攒到合并时再压——因为合并只操作两个根，对中间节点无感知。
典型错误写法是递归 find 里忘了返回压缩后的根，或者用了循环但没更新沿途节点：
立即学习“C++免费学习笔记（深入）”；
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // ✅ 压缩：先递归到底，再回溯时赋值
}
return parent[x];
}
如果写成 return find(parent[x]) 就没压缩；如果用 while 循环但只记了根没改父指针，也白搭。
按秩合并（union by rank）和按大小合并（union by size）怎么选
两者都是优化合并策略，控制树高，配合路径压缩后可使单次 find 均摊接近 O(α(n))。区别在于：
-
rank维护的是近似高度，初始化为 0；合并时把 rank 小的树挂到大的下，相等时才给根的 rank +1 -
size维护子树节点数，合并时把小树挂到大树下，更直观，且后续可支持快速获取连通分量大小
实际中 size 更常用，尤其当需要统计每个集合元素个数时。注意：rank 的“秩”不是真实高度，不能用来判断深度；而 size 是精确值，但不能反映结构平衡性。
示例（按大小合并）：
void unionSet(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) return;
if (size[rootX] < size[rootY]) swap(rootX, rootY);
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
容易被忽略的边界和调试陷阱
实际编码时最常踩的坑不在算法逻辑，而在细节处理：
- 数组越界：
parent下标从 0 开始，但输入点可能从 1 开始编号，记得统一偏移或建 map 映射 - 未初始化
size或rank：只初始化parent不够，size[i]必须初值为 1，rank[i]初值为 0 - 重复调用
find导致冗余：比如if (find(a) == find(b)) unionSet(a, b)里find被算两次，应先存根再用 - 多线程不安全：标准 UnionFind 非线程安全，若需并发访问，得加锁或换用原子操作（但通常并查集用于离线算法，很少真并发）
调试时建议加一个 debugPrint() 打印当前 parent 和 size，比单步看指针更直观。路径压缩是否生效，一眼就能看出链是否变短。
