c++中如何实现并查集UnionFind_c++并查集路径压缩优化_技术教程

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 里忘了返回压缩后的根，或者用了循环但没更新沿途节点：

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 非线程安全，若需并发访问，得加锁或换用原子操作（但通常并查集用于离线算法，很少真并发）