C++实现带路径压缩的并查集优化 _ 集合连通性判定与效率提升【源码】-C++-PHP中文网

find必须递归或迭代+临时变量，因朴素迭代无法回溯更新父指针；路径压缩需在查找根时将路径节点直连根；仅路径压缩均摊o(log n)，加按秩/大小合并才达o(α(n))。

c++实现带路径压缩的并查集优化 _ 集合连通性判定与效率提升【源码】

为什么 `find` 必须写成递归或带临时变量的迭代？

路径压缩的核心是“在查找根节点的同时，把沿途所有节点直接挂到根下”。如果用朴素迭代（只用一个指针一路跳），你无法在回溯时更新父指针——因为没保存路径。所以常见错误是写成：

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

这完全没有压缩。正确做法要么递归（自然回溯）：

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

要么迭代+记录路径：

int find(int x) {
    int root = x;
    while (parent[root] != root) root = parent[root];
    while (x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

递归写法简洁，但深度大时有栈溢出风险（一般 10⁵ 节点内安全）
迭代写法稍长，但可控、无栈开销，适合嵌入式或超大集合
别在 find 里漏掉 return parent[x] —— 压缩后必须返回更新后的根，否则 union 会连错

`union` 操作要不要按秩合并？只靠路径压缩够不够？

只做路径压缩，find 均摊复杂度是 O(log n)，加上按秩合并（或按大小合并）才能降到 O(α(n))，即反阿克曼函数，实际可视为常数。不加的话，极端构造数据（如链状合并）会让树退化，多次 find 变慢。

推荐按大小合并（更直观，无需额外秩数组）：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x]

size 数组初始化为 1，每个节点自成集合时大小为 1
务必先 find 再比较大小，否则合并的是非根节点，破坏结构
如果只关心连通性判定（不查集合大小），可以省略 size，但性能上限会降低

初始化和边界：数组大小、索引从 0 还是 1 开始？

并查集本质是基于数组的森林，下标即节点 ID。C++ 中最易错的是越界和索引偏移：

若节点编号是 1~n，就申请 parent[1 + n]，用 parent[1] 到 parent[n]，别用 vector<int>(n)</int> 然后访问 [i]（会越界）
统一初始化：iota(parent.begin(), parent.end(), 0) 或循环设 parent[i] = i
如果输入含 0 节点，且你用了 vector<int> parent(n)</int>，那 parent[0] 合法；但如果节点是 1~n，用 vector<int> parent(n + 1)</int> 更安全
别在 unite 前忘了判空或判范围——比如读入边时没检查 u, v 是否 ≤ n

怎么验证路径压缩真的生效了？

光看结果正确不够，要确认树高是否被压平。简单办法：在 find 返回前加一句打印（调试时）：

// 调试用，正式提交删掉
if (parent[x] != x && parent[parent[x]] != parent[x]) 
    cout  " 
<p>或者统计每次 <code>find</code> 的跳转次数：</p>
<pre class="brush:php;toolbar:false;">int find(int x) {
    int steps = 0;
    while (parent[x] != x) {
        x = parent[x];
        steps++;
    }
    // 此时 x 是根，再走一遍压缩...
    return x;
}