连通图的判定方法是：从任一顶点出发用dfs或bfs遍历，若能访问所有顶点则连通；或用并查集合并所有边后检查根节点数是否为1；需注意空图（n=0）、单点（n=1）、孤立点、编号离散化及自环重边等边界情况。
用 DFS 或 BFS 遍历一次就能判断
连通图的定义是：无向图中任意两个顶点之间都存在路径。所以只要从任一顶点出发，能访问到所有其他顶点，就是连通图。实际操作就是选一个起点（比如顶点 0），跑一次 DFS 或 BFS，然后检查访问数组是否全为 true。
注意：这个方法只适用于 无向图；有向图要判断“强连通”得用 Kosaraju 或 Tarjan，那是另一回事。
- 邻接表或邻接矩阵都行，
DFS递归写法要注意栈溢出（顶点数 > 1e5 时建议用迭代版或改BFS） - 图不保证编号连续？先做顶点去重映射，再建图
- 输入可能含孤立点（度为 0），它们仍算图的一部分，必须被访问到才算连通
用并查集（Union-Find）边读边判更省心
如果图是动态构建的，或者你不想写遍历逻辑，并查集是更轻量的选择：对每条无向边 (u, v) 调用 union(u, v)，最后检查所有顶点是否属于同一个集合（即根节点数量为 1）。
关键点在于：并查集不关心图结构，只认连通分量个数。初始化时每个顶点自成一集，合并后用 find 统计不同根的数量即可。
- 记得路径压缩 + 按秩合并，否则极端 case 下
find退化成 O(n) - 顶点编号若非 0～n-1，先离散化——用
std::map或排序+去重，别硬开大数组 - 输入边数为 0 且顶点数 > 1？直接返回 false（多个孤立点 → 不连通）
常见错误：忽略图为空或只有一个顶点
边界情况最容易翻车：n == 0（空图）和 n == 1（单点）按定义都是连通图，但有人会误判为 false。
-
n == 0：按数学惯例，空图是连通的（vacuously true），但业务场景可能要求抛异常或返回特殊值，需看题意 -
n == 1：没有边也连通，DFS访问数组长度为 1 且初始就标记，没问题；并查集里根数也为 1 - 输入格式带自环或重边？
DFS/BFS无影响；并查集union(u,u)要防住，加个if (u == v) continue
性能与实操建议：优先 BFS + 邻接表
对大多数 OJ 或工程场景，BFS 比递归 DFS 更稳——没栈溢出风险，缓存友好，代码也干净。邻接表比邻接矩阵省空间，尤其稀疏图。
示例骨架（C++17）：
bool isConnected(int n, const vector<vector>>& graph) {
if (n visited(n);
queue<int> q;
q.push(0);
visited[0] = true;
int count = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
++count;
q.push(v);
}
}
}
return count == n;
}
</int></vector>
图用 vector<vector>></vector> 存，顶点编号 0～n-1；如果输入是边列表，先转邻接表——别在 BFS 里反复扫描边数组。
真正容易被忽略的是：图的存储方式和顶点编号范围必须严格一致。混用 1-indexed 输入和 0-indexed 数组，错位一个下标，整个结果就废了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
