并查集核心是用数组模拟森林，parent[i]==i表示根节点；路径压缩在find中递归返回时更新父指针，按size/秩合并需先找根再连根，避免直接parent[a]=b。
并查集的核心结构怎么写
并查集本质是用数组模拟森林，每个元素存其父节点下标。最简实现不需要额外类封装，直接用 vector<int></int> 就够用：parent[i] == i 表示根节点。
别一上来就写 class + private + find/union 方法——小项目里反而增加理解成本。先跑通逻辑再封装更稳妥。
-
parent初始化为i，即每个点自成集合 - 路径压缩只改
find：递归返回时顺手把沿途节点父指针指向根 - 按秩合并（rank）比按 size 更省空间，但初学用
size更直观
find 函数为什么必须路径压缩
不压缩的 find 退化成链表遍历，单次最坏 O(n)；加了路径压缩后，均摊时间接近 O(α(n))，α 是反阿克曼函数，实际中 ≤ 4。
常见错误是只做一次赋值而不递归更新：
立即学习“C++免费学习笔记（深入）”；
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // ✅ 正确：赋值发生在递归返回后
return parent[x];
}
错写成 return find(parent[x]) 就没压缩效果；或者用 while 循环但忘了最后统一设父节点，也会漏压。
union 操作要避免重复合并和环
两个根相同说明已在同一集合，直接返回，否则会污染 size 或 rank 计数。
- 先
rootA = find(a)，rootB = find(b)，再比较是否相等 - 合并时只连根到根，永远不要写
parent[a] = b—— 这跳过了 find，可能连到非根节点 - 按 size 合并：让小树挂到大树下，代码里是
if (size[rootA]
初始化和边界容易踩的坑
数组大小开错、索引越界、0-indexed 和 1-indexed 混用，是调试中最常卡住的点。
- 若题目给的是 1~n 编号，
parent和size数组长度至少为 n+1，下标 0 不用 - 初始化循环写成
for (int i = 0; i 但实际节点从 1 开始 → 少初始化一个 - C++ 中
vector默认初始化为 0，若用 0 表示“未分配”，就得额外标记数组，不如直接用i初始化安全
并查集真正难的不是写法，而是判断什么时候该用它——比如带撤销的合并、动态连通性、最小生成树 Kruskal 的边排序依赖，这些场景里，find 和 union 的调用时机比实现本身更关键。
