路径压缩是并查集性能保障的关键：find中递归回溯时将路径上所有节点父指针直接指向根，使均摊时间降至O(α(n))，避免长链导致的O(n)最坏情况。
带路径压缩的并查集在 C++ 中不是“要不要加”的问题，而是“不加就大概率超时或出错”的问题——尤其在 union 操作频繁、树深度可能暴涨的场景下，路径压缩能将单次 find 均摊时间压到接近 O(α(n))，而不用它，最坏是 O(n)。
为什么普通 find 会导致性能雪崩？
朴素实现中 find 只是递归/迭代往上找根，不改任何父指针。多次 union 后可能形成一条长链（比如 1→2→3→…→1000），此时每次 find(1000) 都要遍历全部节点。更糟的是，后续所有依赖该节点的 union 或 find 都会重复走这条长链。
路径压缩的核心动作就是在一次 find(x) 返回根的同时，把从 x 到根路径上**所有中间节点**的 parent 直接设为根。不是只改 x，是整条路径“拍平”。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 必须用递归写法才能自然实现“回溯时更新”，迭代写法需额外存路径，易错且无必要
- 不要在
find里做任何副作用（如计数、打印），它应是纯查询+压缩 - 压缩后，
parent[x]不再表示“上一级”，而只是“当前已知的上级”，语义变了
路径压缩 + 按秩合并，两个优化必须一起用吗？
可以只用路径压缩，也能显著提速；但单独用按秩合并（union by rank）效果有限——它只控制树高增长，无法修复已有深链。两者结合才是工业级稳健方案。
关键区别：
-
rank不是真实高度，而是“该子树在未压缩时的上限高度估计”，只在union时用于决定谁当根 - 路径压缩后
rank不再准确，所以绝不拿rank去判断当前深度，只用它指导合并方向 - 如果只关心连通性（不维护 size 或 rank），可省略
rank数组，但性能下限会变低
C++ 实现中容易被忽略的内存与边界细节
常见错误不是算法逻辑错，而是 C++ 特定陷阱：
-
parent和rank数组必须初始化：每个i的parent[i] = i，rank[i] = 0，漏掉任意一个索引都会导致未定义行为 - 数组大小必须严格 ≥ 最大可能节点编号（不是元素个数），比如节点编号是 1~1000，数组就得开 1001，否则
parent[1000]越界 - 使用
std::vector时，构造后立即resize(n+1)，别依赖默认构造值——vector<int>()是空的 - 如果节点编号稀疏（如只有 5, 100, 10000），别硬开大数组，改用
std::map<int, int>存parent，但要注意 map 查找本身有 log 开销
完整可运行源码（含测试用例）
以下是最小可行实现，专注路径压缩本质，无冗余封装：
#include <iostream>
#include <vector>
using namespace std;
struct UnionFind {
vector<int> parent, rank;
UnionFind(int n) : parent(n + 1), rank(n + 1, 0) {
for (int i = 1; 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 (rank[x] < rank[y]) swap(x, y);
parent[y] = x;
if (rank[x] == rank[y]) ++rank[x];
}
bool connected(int x, int y) { return find(x) == find(y); }
};
int main() {
UnionFind uf(10);
uf.unite(1, 2);
uf.unite(2, 3);
uf.unite(4, 5);
cout << uf.connected(1, 3) << " "; // 1
cout << uf.connected(1, 4) << endl; // 0
return 0;
}
注意 find 函数里那行 parent[x] = find(parent[x])——这就是路径压缩的全部。它看起来像简单赋值，实际触发了递归压缩整条链。少一个等号、多一个临时变量，压缩就失效。
