数组实现并查集需初始化parent[i]=i（用std::iota），find必须路径压缩（递归版parent[x]=find(parent[x])，迭代版先找根再回填），union前须判同根，且路径压缩与按大小/秩合并正交共存但顺序不可颠倒。
用数组实现并查集，核心是用一个整型数组 parent[] 表示每个节点的父节点索引。路径压缩不是“额外功能”，而是必须嵌入 find 操作中的结构改造动作——它直接决定后续查找是否高效。
数组初始化与索引对齐必须显式完成
节点编号若从 0 开始（如 n 个点编号为 0 到 n−1），parent 数组就应声明为 vector<int>(n)</int>，并确保每个 parent[i] = i。别依赖默认值，也别用循环逐个赋值；推荐用 std::iota(parent.begin(), parent.end(), 0)，语义清晰且编译器优化友好。若输入节点编号从 1 起，但数组仍按 0 索引分配，访问 parent[x] 前必须减 1，否则越界或逻辑错位。
路径压缩必须在 find 中真正执行，不能只找根
常见错误写法：return parent[x] == x ? x : find(parent[x]); ——这仅递归定位根，未修改任何父指针，路径毫无压缩。正确做法分两种：
-
递归版：写成
return parent[x] = find(parent[x]);。注意是赋值后返回，不是先调用再单独赋值；否则可能被编译器重排或漏执行 -
迭代版：先走到底拿到根
r，再从原节点x出发，沿原路径逐个将parent[i]设为r。虽多一次遍历，但无栈溢出风险，适合大规模数据（如 >10⁵ 节点）
union 操作前必须判同根，否则破坏结构稳定性
合并两个元素 x 和 y，不能直接执行 parent[find(y)] = find(x)。要先算出 root_x = find(x)、root_y = find(y)，再判断 if (root_x != root_y) 才合并。原因有三：
- 避免把已连通集合重复连接，导致树高异常增长，削弱路径压缩效果
- 防止连通分量计数器误减（如维护
count变量时） - 若启用按秩/按大小合并，秩或 size 数组更新逻辑会失效，甚至引发后续 find 返回错误根
路径压缩与按秩/按大小合并可共存，但顺序不能颠倒
两者正交，推荐一起使用。但实现上必须：先用 find 获取两个根，再根据 rank 或 size 决定谁挂谁（即 union 决策），最后所有 find 内部做路径压缩。不能反过来——先压缩再比秩，因为压缩后树高信息已失真，秩不再反映真实高度，仅作启发式参考。实际中，union_by_size 更直观，还天然支持连通块大小查询；union_by_rank 理论更紧，但 rank 数组不可用于 size 推导。
