并查集核心结构是用vector维护parent数组，根节点parent[i]=i；需配合路径压缩与按秩/按大小合并，初始化parent[i]=i、rank[i]=0或size[i]=1，find必须递归或迭代压缩路径，union推荐按秩合并以控制树高。
并查集的核心结构怎么写
并查集本质是用树表示集合，每个节点存父节点下标，根节点指向自己。C++里最常用的是 vector 存 parent 数组，配合路径压缩和按秩合并实现接近常数时间复杂度。
典型初始化：每个元素初始独立成集，parent[i] = i；rank[i] = 0（仅用于按秩合并）。
-
find必须带路径压缩：递归或迭代把沿途节点直接挂到根下 -
unionSets推荐用按秩合并（不是按大小），避免树退化；若用 size 合并，需额外维护vector记录集合大小 - 别在
find里返回引用或修改原数组以外的状态，否则多线程不安全（单线程可忽略）
find 函数为什么一定要路径压缩
不压缩时，find 可能退化为 O(n)，比如链状结构反复 union；路径压缩后，单次 find 均摊接近 O(α(n))，α 是反阿克曼函数，实际中 ≤ 4。
常见错误写法：return parent[x] = find(parent[x]) 是标准递归压缩；但有人写成 parent[x] = find(parent[x]); return parent[x];，逻辑等价，可读性略好。
立即学习“C++免费学习笔记（深入）”；
- 迭代写法更省内存：用临时 vector 记录路径，再统一更新父指针
- 不要在压缩时改
rank或size——这些只在 union 阶段更新 - 如果只做查询不关心树形态，甚至可以只做「一次压缩」（find 时压一层），但标准模板建议全压
unionSets 怎么选按秩还是按大小合并
按秩（rank）合并指比较根节点的树高，小树挂大树下；按大小（size）是比集合元素个数。两者都能保证树高 ≤ log n，但 rank 更省空间（不用额外 size 数组），size 对某些题型（如求连通块大小）更方便。
注意：rank 不是真实高度，只是上界估计值，只有在两子树 rank 相等时才对新根 rank++。
- 用 rank：初始化
rank.resize(n, 0)，合并时只在rank[rx] == rank[ry]时rank[rx]++ - 用 size：初始化
size.resize(n, 1)，合并后size[rx] += size[ry] - 别混用：同时维护 rank 和 size 没必要，徒增出错概率
实际编码时容易漏掉的边界
输入索引常从 0 或 1 开始，但并查集下标必须连续且覆盖全集；遇到离散化 ID（如字符串、大整数）必须先映射到 [0, n) 范围。
常见报错：std::out_of_range（vector 下标越界）、find 返回负值（初始化漏设 parent[i] = i）、union 后忘记调用 find 获取根（直接用原始 x/y 判断是否同集）。
- 调试技巧：加个
debugPrint函数，输出每个点的find(i)结果，快速验证连通性 - LeetCode 类题目常要求返回连通分量数量，可在 union 时用计数器：初始
count = n，每次成功合并减 1 - 别在构造函数里预分配过大的 vector（如 1e6+），除非确定要用；动态 resize 更稳妥
并查集真正难的不是写法，而是判断什么时候该用它——看到“合并集合”“查询是否连通”“动态连通性”就得条件反射想 find 和 unionSets，而不是硬套 DFS/BFS。
