并查集核心结构是用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 对某些题型（如求连通块大小）更方便。
