并查集核心是用数组模拟森林，parent[i]=i初始化，必须同时使用路径压缩与按秩合并优化；find推荐迭代实现，union需先find再合并，优先使用vector管理内存。
并查集的核心结构怎么写
并查集本质是用数组模拟森林，每个节点存它的父节点下标。初始化时让 parent[i] = i，表示每个元素自成一个集合。关键不是“树”，而是「路径压缩 + 按秩合并」两个优化必须一起用，否则退化成链表，find 可能 O(n)。
常见错误：只做路径压缩不按秩合并，或反过来；或者把 rank 当成树高来维护却没处理合并时的相等情况。
-
find必须递归或迭代实现路径压缩（推荐迭代，避免栈溢出） -
unionSets要比较rank，小树挂到大树下；相等时才给大树rank++ -
rank数组初始全 0，它不是真实高度，只是上界估计，所以叫rank比height更准确
标准 find 和 union 实现细节
迭代版 find 更安全，尤其数据量大时。别用递归——C++ 默认栈空间有限，10⁵ 级别节点容易爆栈。
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径压缩：直接连到祖父
x = parent[x];
}
return x;
}
unionSets 里要先 find 再合并，否则可能把两个不同集合的根直接连错。别漏掉这步。
- 必须对两个参数都调用
find，得到真正的根 - 合并时只改一个根的
parent，另一个根的rank不变 - 如果两根相同，说明已在同一集合，直接返回，不操作
什么时候该用 vector 还是 new int[]
现代 C++ 优先用 std::vector<int></int> 管理 parent 和 rank。手动 new 容易忘 delete，且无法自动扩容。但要注意：vector 的下标从 0 开始，若题目节点编号是 1~n，就开 vector<int>(n+1)</int>，用 [1] 到 [n]。
- 初始化：用
vector<int>(n+1)</int>，然后循环i=1到n设parent[i] = i - 不要用
resize(n)后从 0 开始用——容易和题干编号对不上，调试极难定位 - 如果确定 n 很大（如 1e6）且生命周期明确，用
std::unique_ptr<int></int>比裸指针更安全
常见报错和调试线索
最常遇到的是 segmentation fault，基本就是数组越界：要么下标用了 0~n-1 却按 1~n 访问，要么 find 里没检查 x 是否在合法范围内。
另一个典型问题是「合并了但查询没更新」：比如调了 unionSets(a, b)，之后却查 find(a) 和 find(c)，而 c 根本没参与任何操作——这不是算法错，是逻辑漏了关联。
- 调试时先打一行
cout 看前几步是否符合预期 - 检查输入：有些题用 0-indexed 输入，有些用 1-indexed，别硬套模板
- 注意并查集不支持「删边」或「撤销合并」，需要这些功能得换 LCT 或可持久化 DSU
find 的路径压缩那行 parent[x] = parent[parent[x]] 容易手误写成 parent[x] = parent[x]，这种 bug 编译不报错，但集合永远不合并。多看一眼。C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
