路径压缩需递归先找到根再赋值，确保查找路径上所有节点直连根；union前必须检查连通性以防冗余操作和rank失真；按秩合并与路径压缩可共存且应共用，共同实现近乎常数时间复杂度。
路径压缩在 find 中怎么写才不破坏并查集语义
路径压缩的核心目标是：让查找过程中经过的所有节点，**直接指向根节点**，而非仅更新父指针链上的某一层。但常见错误是只改了当前节点的 parent，没递归修正整条路径——这会导致后续 find 仍要遍历旧链，压缩失效。
正确做法是「递归 + 赋值」：先递归找到根，再把当前节点的 parent 设为该根。这样每层返回时都完成一次直连。
- 必须用递归（或显式栈模拟），不能只改
parent[x]后就返回parent[x] - 避免在递归前修改
parent[x]，否则会切断查找路径，导致返回错误根 - 若用迭代实现，需先走到底记录所有路径节点，再反向统一设为根
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 关键：先递归得根，再赋值压缩
}
return parent[x];
}
union 操作里要不要检查是否已连通
不做检查也能工作，但会带来两方面问题：一是冗余调用 find，二是可能破坏按秩合并（union by rank）的树高控制逻辑，间接削弱路径压缩效果。
实际中几乎总是需要检查。因为并查集常用于图的连边判定（如 Kruskal）、去重合并等场景，重复合并同一连通分量不仅无意义，还可能让 rank 失真（比如误增高度）。
- 必须在
union开头调用两次find，获取两个根 - 若两根相等，直接返回
false或跳过合并 - 若启用按秩合并，只在根不同时更新
rank：仅当两子树秩相等时，被挂载方的秩才 +1
按秩合并和路径压缩能一起用吗？会不会冲突
能，而且强烈建议一起用。两者解决不同问题：路径压缩优化单次 find 时间，按秩合并控制树高增长，共同将均摊时间压到近乎常数（阿克曼函数反函数级别）。它们不冲突，因为 rank 只用于合并决策，不参与路径压缩逻辑；压缩后 rank 不再严格等于真实高度，但仍是上界估计，足够支撑合并策略。
-
rank数组应初始化为 0，不是 1 - 路径压缩后，某个节点的
rank值不再反映其子树实际深度，所以绝不能用rank[x]判断高度 - 合并时只比较两根的
rank值，与路径压缩无关
完整可运行的 C++ 实现要注意哪些边界细节
一个看似简单、实则容易翻车的点是：初始化时 parent[i] = i 必须覆盖全部有效索引，且 rank 数组长度要对齐。另外，C++ 中若用 vector 动态分配，下标从 0 开始，但业务节点编号可能从 1 开始——这里极易越界或漏初始化。
- 构造函数中，
n表示节点总数，parent和rank都应开n+1（支持 1~n 编号）或严格按输入范围对齐 -
count（连通分量数）初始为n，每次成功union后减 1；注意仅在两根不同时才减 - 返回布尔值的
union函数，推荐命名unite或merge，避免与关键字union冲突 - 不要在
find里做count更新，它只负责查找
struct UnionFind {
vector<int> parent, rank;
int count;
UnionFind(int n) : parent(n + 1), rank(n + 1, 0), count(n) {
for (int i = 1; i
路径压缩真正起效的前提，是同一个连通分量被反复查询；而按秩合并的收益，在于第一次合并就控制住了结构膨胀。这两者在代码里只是几行赋值和比较，但漏掉任一条件（比如忘记 <code>swap</code>、误判 <code>rx == ry</code>、初始化错长度），都会让复杂度退化回 O(n) 级别。</int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
