并查集基础结构用数组模拟父节点最稳妥，parent[i]初始化为i；find需路径压缩且避免递归栈溢出；按秩合并的秩是树高上界估计值，非真实高度；完整模板应封装parent、rank并配套使用两种优化。
并查集基础结构怎么写才不容易出错
直接用数组模拟父节点关系最稳妥，parent[i] 表示节点 i 的父节点，初始化时设为自身。别用指针或动态对象——C++ 里下标访问快、内存连续、无构造析构干扰。
常见错误是把 find 写成递归但没处理栈溢出（尤其数据量大时），或者忘了在查找后更新父节点（路径压缩失效）。
-
parent数组大小必须 ≥ 最大可能节点编号（推荐从 0 或 1 开始统一编号） - 初始化必须显式循环赋值：
parent[i] = i，不能靠全局变量默认零初始化（除非你确定节点编号从 0 开始且全用上） - 合并操作前先
find两次，比较根而非原编号
路径压缩为什么必须写在 find 里而不是 union 里
路径压缩本质是“懒更新”：只在查询根时顺手压平路径。如果只在 union 里做，那中间多次 find 仍走长链，时间复杂度退化到 O(n)。
正确做法是在 find 返回前，把当前节点的父节点直接设为根——注意不是返回根，而是改 parent[i]，再返回。
立即学习“C++免费学习笔记（深入）”；
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 递归压缩：先压子树，再设自己父为根
}
return parent[x];
}
非递归写法更省内存（防爆栈），但要多一次遍历找根再二次遍历改父：
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
按秩合并的“秩”到底该存什么
这里的“秩”不是真实树高，而是**上界估计值**，仅用于决定合并方向。用 rank[i] 表示以 i 为根的树的近似深度，初始全为 0。合并时，总把秩小的树挂到秩大的根下；相等时任选其一，被挂方秩 +1。
关键点：秩只增不减，且永远 ≤ 实际树高；它和路径压缩可共存，但压缩后秩不再反映真实结构——这没关系，因为秩只服务合并决策。
- 别把
rank和节点数量（size）混用：按大小合并（union-by-size）是另一种优化，效果接近但语义不同 - 如果同时用路径压缩 + 按秩合并，均摊时间复杂度是 O(α(n))，α 是反阿克曼函数，实际中 ≤ 4
- 调试时可打印
rank[root]观察是否合理增长，但别拿它当树高用
完整带优化的并查集模板怎么组织
把 parent 和 rank 封装进 class，避免裸数组越界或生命周期错乱。构造函数接收节点数，强制初始化；提供 unite（非对称命名比 merge 更准）、same、size（需额外维护 sz[]）等接口。
容易忽略的是：按秩合并与路径压缩必须配套使用才能达到最优；单独用路径压缩已够快，但加秩合并能进一步减少树高波动。
class UnionFind {
vector parent, rank;
public:
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) swap(x, y);
parent[y] = x;
if (rank[x] == rank[y]) ++rank[x];
}
bool same(int x, int y) { return find(x) == find(y); }
};
实际用的时候，别在 unite 里反复调 find ——上面模板已确保每次只查一次根。如果业务需要统计连通块大小，就加 vector 并在 unite 里同步更新。
