如何将C语言实现带路径压缩的并查集算法改写为长尾关键词？

本文共计1115个文字，预计阅读时间需要5分钟。

非递归写法（例如while循环+栈模拟）容易漏掉根节点，导致压缩不彻底。递归天然而然保证：

常见错误是写成「先改当前节点 parent，再调 find(parent)」，这会跳过中间层更新。正确做法是先递归获取根，再统一赋值：

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 先递归到底，再回写 } return parent[x]; }

• 必须用 parent[x] = find(parent[x])，不能写成 find(parent[x]); parent[x] = root（root 未定义）
• 如果用迭代，需两遍扫描：第一遍找根，第二遍从 x 向上逐个重连，代码更长且易错
• gcc/clang 对这种尾递归有一定优化，深度 10⁵ 一般不会栈溢出；若真担心，可加编译器 pragma 或手动扩栈

unionSets 里要不要按秩合并？不加会怎样？

不加按秩合并（即只做 parent[rootY] = rootX），最坏情况下树退化成链，find 退化为 O(n)，路径压缩虽能缓解单次查询，但连续 union+find 混合操作时，均摊性能仍不如带秩合并。

按秩合并本质是控制树高，和路径压缩正交互补。两者共用才能达到近乎 O(α(n)) 的均摊复杂度（α 是反阿克曼函数，实际 ≤ 4）。

立即学习“C++免费学习笔记（深入）”；

• 秩（rank）不是高度，而是该子树作为根时的「上限高度估计」，初始化为 0
• 合并时，总是把 rank 小的树挂到 rank 大的树下；相等时才给目标根 rank+1
• 路径压缩不改变 rank 值——它只改 parent，不影响秩维护逻辑

如何判断两个点是否连通？别直接比 parent[a] == parent[b]

这是新手最高频误操作。parent[a] 和 parent[b] 可能都不是根，直接比较毫无意义。必须先调用 find(a) 和 find(b)，再比返回值。

典型错误场景：刚 union 过，但没对 a、b 各自执行 find，就去查 parent 数组——此时路径尚未压缩，parent 值可能指向中间节点，导致误判断开。

• 连通性判定唯一可靠方式：find(a) == find(b)
• 不要缓存 find 结果用于后续多次比较——除非你确认期间无 union 操作，否则可能 stale
• 如果频繁查连通性，可考虑在 union 后立刻对涉及节点调用 find 强制压缩，避免后续重复计算

数组 vs vector？初始化大小写错会触发什么错误？

用 vector<int> parent(n) 时，若 n 传错（比如传了 0 或负数），构造后 parent.size() == 0，后续 find(0) 直接越界访问——C++ 不检查 vector 下标，行为未定义，大概率段错误或静默脏读。

用原生数组（如 new int[n]）更危险：忘了初始化 parent[i] = i，所有值是随机垃圾，find 会跳到非法内存地址。

• 务必在构造并查集时，对索引 0 到 n−1 执行 parent[i] = i
• 推荐用 vector + iota(parent.begin(), parent.end(), 0)，简洁且不易漏
• 如果节点编号不连续（如 ID 是字符串或大整数），得换哈希表实现，但路径压缩逻辑不变，只是 parent 改成 unordered_map<int, int>

实际用的时候，最容易被忽略的是：路径压缩只在 find 里发生，unionSets 自己从不压缩。这意味着，如果你只 union 不 find，parent 树可能一直很“毛”，某次突然 find 会触发一次长链压缩——这本身没问题，但若误以为“union 后 parent 已扁平”，就会在调试时困惑为什么两次 find 返回一样却 parent 数组看起来没变。