必须显式完成路径压缩且与按大小合并共存才能达到O(α(n))；仅路径压缩最坏O(log n)，未显式压缩或不配合合并均无法真正高效。
不加路径压缩的 find 在 10⁵ 级操作下大概率超时；只加路径压缩但不配合按大小/秩合并，均摊复杂度卡在 O(log n)，不是真正意义上的高效。
为什么 find 必须显式完成路径压缩，不能只靠递归调用？
常见错误是写成：return parent[x] = find(parent[x]);。C++ 标准不保证赋值右侧先求值，部分编译器可能先取 parent[x] 再调用 find，导致未定义行为。更隐蔽的问题是：即使侥幸执行，若中间某次 find 返回前没更新 parent[x]，该节点仍指向旧父节点，下次查询还得走长链。
正确做法分两步：
- 先递归到底拿到真实根节点
root - 回溯时统一设
parent[x] = root，再返回root
示例（安全递归）：
int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]);
parent[x] = root;
}
return parent[x];
}
unionSet 里不先 find 就直接合并，会破坏结构
合并操作本质是「把一棵树的根挂到另一棵树的根下」。如果跳过 find 直接用原始输入 x、y 做判断或赋值，极大概率操作的是非根节点，导致森林分裂或环——后续所有 find 都返回错误根。
必须严格遵循顺序：
- 先
x = find(x)、y = find(y) - 判等：若
x == y，直接返回 - 再比较
size[x]和size[y]（或rank[x]和rank[y]），小树根挂大树根 - 更新
size或rank：仅更新新根的值，非根节点的size/rank不动
用 vector 存 parent 和 size 是最稳起点
别用 map 模拟稀疏节点——find 平均变慢，且破坏 O(1) 随机访问前提。真有大整数 ID，先离散化映射到 0~n-1。
初始化关键点：
- 数组大小必须 ≥ 最大可能节点数，
vector构造时就resize(n)或reserve(n) - 索引统一用 0-based：输入是 1~n 的编号，读入后立刻
a--、b-- -
parent[i] = i、size[i] = 1必须覆盖全部n个下标，漏一个就段错误或逻辑错
路径压缩和按大小合并必须共存，才能逼近 O(α(n))
只做路径压缩，最坏情况仍是 O(log n) —— 比如反复将小链挂到大树末端，树高仍可累积。按大小合并确保每次合并都让小树服从大树，天然抑制深度增长。
size 比 rank 更推荐，因为：
-
size始终真实反映子树节点数，不受路径压缩影响 - 支持后续查连通分量大小：
size[find(x)]即为x所在集合元素个数 - 无需额外维护失真的
rank值，代码更直白
容易被忽略的一点：路径压缩发生在 find 里，按大小合并发生在 unionSet 里，二者触发时机不同、作用对象也不同——压缩改的是查询路径上的所有节点，合并只动两个根。混在一起处理，反而容易漏压或误合。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
