数组实现并查集更轻量，避免动态内存分配和空指针风险，适合竞赛或嵌入式场景；节点编号连续，天然适配下标，但大小固定需预知最大节点数N。
为什么不用指针而用数组实现并查集
数组实现比指针更轻量，避免动态内存分配和空指针风险，适合竞赛或嵌入式场景；所有节点编号从 0 或 1 开始连续，天然适配数组下标。但缺点是大小固定，初始化时就得知道最大节点数 N。
核心思路：用一个整型数组 parent[] 存每个节点的父节点编号，初始时 parent[i] = i（自己是根）；再配一个 rank[]（或 size[]）辅助优化合并策略。
-
parent数组必须声明为全局或足够大的静态数组（如int parent[100005]），不能用vector动态扩容——否则路径压缩后下标可能越界 - 若用按秩合并（
rank），rank[i]表示以i为根的树的高度上界；若用按大小合并（size），size[i]表示子树节点数，仅当i是根时有效 - 不要在
find中直接写parent[x] = find(parent[x])——C++ 求值顺序未定义，可能造成错误赋值；应先算出根再赋值
怎么写带路径压缩的 find 函数
路径压缩的目标是把查找路径上所有节点的 parent 直接连到根，下次查就 O(1)。关键在于「先递归找根，再统一改父」，不是边递归边改。
int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]);
parent[x] = root;
}
return parent[x];
}
- 不能写成
return parent[x] = find(parent[x])——虽然常见于模板，但在某些编译器或开启严格别名检查时可能触发未定义行为 - 如果用非递归版本，需手动维护栈或用 while 循环两次遍历（先上溯找根，再回溯设父），代码更长但无栈溢出风险
- 注意：路径压缩后
rank值不再严格等于树高，所以按秩合并只能作为启发式，不能依赖其精确性
union 操作里按大小合并 vs 按秩合并怎么选
两者都是为了控制树高，摊还复杂度同为 O(α(n))，但实际表现有差异：按大小合并更容易理解且调试友好；按秩合并节省一个数组空间（rank 通常只用 1 字节），但合并逻辑稍绕。
立即学习“C++免费学习笔记（深入）”；
// 按大小合并（推荐初学用）
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
}
- 按大小合并时，务必保证只更新根节点的
size值；非根节点的size值已失效，不可读 - 按秩合并中，只有当两棵树秩相等时才提升新根的
rank，其他情况不更新：if (rank[a] == rank[b]) rank[a]++; - 混用两种策略会破坏复杂度保证——比如一边用
size合并，另一边又读rank判断，结果不可预测
常见错误：初始化漏掉 rank/size 或写错边界
最常踩的坑不是算法逻辑，而是初始化疏忽。比如节点编号从 1 到 n，却把循环写成 for (int i = 0; i ，导致 <code>parent[0] 被误设、parent[n] 未初始化。
- 初始化必须覆盖全部可能用到的下标：若节点编号范围是
[1, n]，则循环写for (int i = 1; i ，且 <code>parent[i] = i、size[i] = 1、rank[i] = 0 - 数组大小至少为
n + 1（下标 0 不用也要留空位），否则访问parent[n]会越界 - 调用
find前没确认输入编号是否在合法范围内——比如读入数据含0或大于n的数，直接访问数组就崩
路径压缩和合并策略本身不难，真正卡住人的永远是下标、初始化、边界这三处。写完先拿 3 个节点手模一遍 unite(1,2)、unite(2,3)、find(3)，看 parent 和 size 数组变没变对，比跑样例更快定位问题。
