并查集用vector实现路径压缩find和按秩合并unionSet：初始化parent[i]=i、rank全0；find递归压缩路径；unionSet先判同根，再按秩合并，秩等时新根秩+1。
用 vector 实现带路径压缩的 find 和按秩合并的 unionSet
并查集核心就两个操作：找根（find）和合并（unionSet）。C++ 里最常用的是用 vector<int></int> 存父节点，下标是节点编号，值是它的直接父节点。初始化时每个点指向自己：parent[i] = i。
路径压缩在 find 里做：递归找到根后，把沿途所有节点的父指针直接连到根上。按秩合并（rank）避免树退化成链表——只把矮树挂到高树下。注意 rank 不是真实高度，只是上界估计，所以叫“秩”更准确。
class UnionFind {
vector<int> 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) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
void unionSet(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) swap(rx, ry); // 确保 rx 是更高/不矮的根
parent[ry] = rx;
if (rank[rx] == rank[ry]) rank[rx]++; // 高度相等才+1
}
};
为什么不用 map 存非连续编号节点？
如果节点编号稀疏或不是整数（比如字符串 ID），确实有人想用 map<string string></string> 或 unordered_map。但这样会带来三个实际问题：
-
find递归调用时哈希查找开销变大，路径压缩收益被抵消 - 无法预分配空间，
rank也得用map维护，逻辑变重 - 很多题目输入保证编号是
0..n-1，强行用map属于过早优化
真要处理字符串节点，先离散化映射到 0..k-1 再用 vector 版本，比全程哈希快且稳。
立即学习“C++免费学习笔记（深入）”；
unionSet 里漏判 rx == ry 会导致什么？
常见错误是合并前没检查是否已同属一个集合，直接执行 parent[ry] = rx。后果是：
- 可能把某棵树的根错误地设为自己子节点（比如
rx == ry时parent[rx] = rx看似无害，但后续rank更新会错乱） - 如果代码里有计数逻辑（如维护连通分量数量），不提前
return就会多减一次 - 某些 OJ 题目卡常，重复合并会拖慢
find效率（虽然路径压缩能缓解，但没必要）
所以 if (rx == ry) return; 这行不能省，它不是防御性编程，而是逻辑必需。
静态数组 vs vector：竞赛和工程场景怎么选？
算法题里一律用 vector，因为大小在运行时才知道；但嵌入式或性能极端敏感场景，可能用 std::array 或裸数组（如 int parent[100005]）。
关键区别在于：
-
vector构造/析构有少量开销，但支持动态扩容（虽然并查集不需要） - 裸数组必须编译期确定大小，写死上限容易溢出，写太大又浪费内存
-
std::array折中，但无法传参推导大小，接口不如vector自然
除非明确知道最大节点数且对启动时间极度敏感，否则别为了省几十纳秒改用静态数组——调试成本和可读性损失更大。
