并查集通过find和union操作维护动态连通性，初始化各节点为独立集合，对每条边执行unite，最终统计不同根节点数得连通分量个数；需路径压缩与按size合并以保效率。
用并查集判断图连通性，核心是 find 和 union 操作
并查集（Union-Find）不是图遍历算法，而是高效维护动态连通关系的数据结构。它不直接“求连通分量”，但能快速回答「两点是否连通」，并在所有边处理完后，通过统计不同根节点数量得到连通分量个数。
关键点：初始化每个节点为独立集合；对每条无向边 (u, v) 执行 union(u, v)；最终调用 find(i) 统计不同根的数量。
-
find必须带路径压缩，否则多次查询可能退化成 O(n) -
union推荐按秩合并（或按 size 合并），避免树过高 - 输入边时注意节点编号是否从 0 或 1 开始，影响数组大小分配
c++ 并查集标准实现（含路径压缩 + 按 size 合并）
下面是一个生产可用的轻量级实现，支持快速构建和连通分量计数：
struct UnionFind {
vector<int> parent, size;
int components;
UnionFind(int n) : parent(n), size(n, 1), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
components--;
}
bool connected(int x, int y) { return find(x) == find(y); }
};
使用示例：读入 n 个点、m 条边后统计连通分量数
立即学习“C++免费学习笔记（深入）”；
用于自动切换项目中适合的node 版本
下载
根据 package.json 中的 engines 字段自动检测 Node.js 版本需求，未安装 nvm 时自动安装并切换至对应版本。支持 Windows、macOS、Linux。适用于 Node.js 项目开发、版本切换和环境配置。
int n, m; cin >> n >> m;
UnionFind uf(n);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
uf.unite(u, v); // 假设节点编号为 0~n-1
}
cout << uf.components << endl;
如何获取每个连通分量的具体节点列表
components 字段只给总数，若需输出每个分量包含哪些点，得额外做一次分组：
- 遍历所有节点
i，用find(i)得到其根 - 用
map<int vector>></int>或vector<vector>></vector>收集相同根的节点 - 注意：根不一定是原始编号，但每个分量内所有
find(i)返回值一致
简写示例：
map<int, vector<int>> groups;
for (int i = 0; i < n; i++) {
groups[uf.find(i)].push_back(i);
}
for (auto& [root, nodes] : groups) {
cout << "Component: ";
for (int x : nodes) cout << x << " ";
cout << "\n";
}
容易忽略的边界与性能坑
实际编码中这几个点最常出错：
- 节点编号若从 1 开始，
UnionFind uf(n)没问题，但读入后要u--, v--再传入 - 重边（重复的
(u,v)）不会破坏正确性，但unite中的if (x==y) return能避免冗余操作 - 离线静态图用并查集比 DFS/BFS 略快且内存更省；但若需实时删边，就得换动态图算法（如 ETT 树）
- 初始化
parent用iota比循环赋值更简洁安全
连通分量本身没有顺序，但各分量内节点顺序取决于你遍历 0..n-1 的方式——这点在调试输出时容易让人误以为结果“不稳定”。
