c++中如何求图的连通分量_c++并查集实现图连通性判断-C++-PHP中文网

c++oding="utf-8" ?>

并查集通过find和union操作维护动态连通性，初始化各节点为独立集合，对每条边执行unite，最终统计不同根节点数得连通分量个数；需路径压缩与按size合并以保效率。

c++中如何求图的连通分量_c++并查集实现图连通性判断

用并查集判断图连通性，核心是 `find` 和 `union` 操作

并查集（Union-Find）不是图遍历算法，而是高效维护动态连通关系的数据结构。它不直接“求连通分量”，但能快速回答「两点是否连通」，并在所有边处理完后，通过统计不同根节点数量得到连通分量个数。

关键点：初始化每个节点为独立集合；对每条无向边 (u, v) 执行 union(u, v)；最终调用 find(i) 统计不同根的数量。

find 必须带路径压缩，否则多次查询可能退化成 O(n)
union 推荐按秩合并（或按 size 合并），避免树过高
输入边时注意节点编号是否从 0 或 1 开始，影响数组大小分配

c++ 并查集标准实现（含路径压缩 + 按 size 合并）

下面是一个生产可用的轻量级实现，支持快速构建和连通分量计数：

用于自动切换项目中适合的node 版本

根据 package.json 中的 engines 字段自动检测 Node.js 版本需求，未安装 nvm 时自动安装并切换至对应版本。支持 Windows、macOS、Linux。适用于 Node.js 项目开发、版本切换和环境配置。

下载

components

遍历所有节点 i，用 find(i) 得到其根
用 map> 或 vector> 收集相同根的节点
注意：根不一定是原始编号，但每个分量内所有 find(i) 返回值一致

简写示例：

map<int vector>> groups;
for (int i = 0; i <h3>容易忽略的边界与性能坑</h3>
<p>实际编码中这几个点最常出错：</p>
<ul>
<li>节点编号若从 1 开始，<code>UnionFind uf(n)</code> 没问题，但读入后要 <code>u--, v--</code> 再传入</li>
<li>重边（重复的 <code>(u,v)</code>）不会破坏正确性，但 <code>unite</code> 中的 <code>if (x==y) return</code> 能避免冗余操作</li>
<li>离线静态图用并查集比 DFS/BFS 略快且内存更省；但若需实时删边，就得换动态图算法（如 ETT 树）</li>
<li>初始化 <code>parent</code> 用 <code>iota</code> 比循环赋值更简洁安全</li>
</ul>
<p>连通分量本身没有顺序，但各分量内节点顺序取决于你遍历 <code>0..n-1</code> 的方式——这点在调试输出时容易让人误以为结果“不稳定”。</p></int>