路径压缩需与按秩合并共用才能达O(α(n))；find必须显式更新父指针，安全写法为return parent[x]==x?x:parent[x]=find(parent[x])；union前须检查连通性，数组初始化要匹配编号范围。
只做路径压缩，find 最坏仍是 O(log n)；必须和按大小（或按秩）合并共用，才能稳定逼近 O(α(n)) —— 这不是可选项，是性能底线。
为什么 find 必须显式更新父指针，不能只靠递归调用
常见错误写法：return find(parent[x]) 或 parent[x] = find(parent[x])（未加括号保护求值顺序）。C++ 标准不保证赋值右侧先执行，部分编译器可能先读 parent[x]、再调用 find，导致中间节点没被更新。
真正生效的路径压缩，必须确保「当前节点的 parent[x] 在返回前被设为真实根」。安全做法分两步：
- 先递归拿到根：
int root = find(parent[x]) - 再显式赋值：
parent[x] = root - 最后返回：
return root
等效简洁写法：return parent[x] == x ? x : parent[x] = find(parent[x]) —— 注意这里 = 是表达式的一部分，且优先级低于 ?:，语义明确。
立即学习“C++免费学习笔记（深入）”；
union 前不检查是否已连通会出什么问题
跳过 if (find(x) == find(y)) return 直接合并，表面不影响连通性，但会破坏结构稳定性：
-
size或rank数组被误更新：比如两集合本就联通，却把小树 size 错加到大树下，后续size[find(x)]返回错误值 - 连通分量计数多减一次：很多题目依赖
count--统计剩余块数，漏判就直接错 - 按秩合并逻辑失效：若两树
rank相等，本不该递增却执行了rank[root]++，树高上界失真
正确流程始终是：int rx = find(x), ry = find(y); if (rx == ry) return; // 后续合并。别用 parent[x] == parent[y] 判定——未压缩时完全不可靠。
数组初始化和索引偏移最容易踩的坑
90% 的段错误和静默逻辑错，来自初始化和编号不匹配：
- 输入节点编号是
1~n，但声明vector<int> parent(n)</int>，然后直接用parent[u]→ 越界访问 - 声明
parent(n + 1)却只初始化i = 1到n，漏掉parent[0]→ 若某处误传0，它仍为0，造成虚假自环 - 用
std::iota(parent.begin(), parent.end(), 0)比循环赋值更安全，语义清晰且编译器优化好
统一建议：vector<int> parent(n + 1), size(n + 1, 1); for (int i = 1; i 。所有输入读入后立刻减一（<code>u--）或加一（视编号起点），保持内部全用 0-based 或全用 1-based，别混用。
迭代版 find 怎么写才不丢压缩效果
递归版在 n ≤ 1e5 时足够安全；但若担心栈溢出（比如链状初始数据 + 深度 > 1e6），必须用迭代，且必须两遍遍历：
- 第一遍：找到根节点
root，不改任何parent - 第二遍：从原始
x出发，用临时变量保存下一个节点：int next = parent[x]; parent[x] = root; x = next;，直到x == root
漏掉第二遍，等于只做了查找，没做压缩。别尝试“边找边压”，比如 parent[x] = parent[parent[x]] —— 容易指向中间节点，最终返回非根，整个并查集逻辑崩溃。
