带路径压缩的 find 函数应采用迭代法：先遍历至根节点，再回溯将路径上所有节点直接指向根，兼顾安全性与效率，避免递归栈溢出和单层压缩导致的性能退化。
怎么写一个带路径压缩的 find 函数
不带路径压缩的 find 会导致树退化成链表，查询变成 O(n)；实际项目里几乎没人用纯递归或纯迭代但不压路径的版本。
推荐用迭代 + 路径压缩：先遍历到根，再回扫一遍把沿途节点全指向根。比递归更安全（避免栈溢出），比单次遍历更高效（后续查询接近 O(1)）。
- 别直接递归写
find(x) { return parent[x] == x ? x : find(parent[x]); }—— 缺少压缩，白写了 - 别在压缩时只改一层（比如
parent[x] = parent[parent[x]]），这是“隔代压缩”，效果差很多 - 初始化时确保
parent[i] = i，否则find会读到未定义值，尤其用 vector 时容易漏初始化
union 操作里要不要按秩合并
要。按秩合并（union by rank）和路径压缩是并查集性能保障的两个支柱，缺一不可。不按秩，最坏情况树高仍可能接近 n；只按秩不压缩，查询仍是 O(log n)；两者合用才摊还 O(α(n))。
“秩”不是真实高度，而是上界估计，所以用 rank 数组存整数就行，更新规则简单：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 合并前比较
rank[rootA]和rank[rootB] - 谁大，谁当爹；相等时任选一个当爹，并给它的
rank+1 - 别用
size替代rank后忘了改逻辑——按大小合并（union by size）也可以，但那是另一套规则，混用会破坏复杂度保证
为什么 std::vector<int> 比 int[] 更适合存 parent 和 rank
图论题输入规模不确定，节点编号常从 1 开始、不连续、甚至带偏移（比如 100000 ~ 200000）。用原生数组得手动算偏移+开大缓冲区，容易越界或浪费内存。
-
vector可以resize(n + 1)，索引直接对应节点编号，不用脑子换算 - 构造函数里初始化
parent[i] = i很自然，rank全设为 0 也一行搞定 - 传参时用引用（
const vector<int>& parent）避免拷贝，性能无损 - 别用
new int[n]手动管理——忘了delete[]就泄漏，而且不能自动扩容
常见报错：Segmentation fault 或 index out of bounds
八成是节点编号没对齐。比如题目说“n 个点，编号 1~n”，你却把 parent[0] 当作节点 1，或者循环写了 for (int i = 0; i < n; ++i) 却用 i 当节点号去查 parent[i]。
- 统一约定：节点编号即数组下标，开
vector<int> parent(n + 1)，只用1..n的下标 - 读入边时立刻做检查：
if (u < 1 || u > n || v < 1 || v > n)，早报错早调试 - 用
assert在 debug 版本里卡住可疑访问，比如assert(x >= 0 && x < parent.size())放在find开头
