判定一个无向图是否为连通图。 连通图的定义如下:图中任意两个顶点之间都是连通的,即存在路径。 若是连通图,输出‘Yes’;若不是连通图,输出其连通分量的个数。
时间: 2024-03-27 08:36:44 浏览: 30
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决这个问题。首先,我们可以任选一个节点进行搜索,如果遍历到了所有节点,那么这个图就是连通图;如果遍历到的节点数量小于总节点数,那么这个图就不是连通图,可以通过多次搜索不同的节点来计算连通分量的个数。
以下是使用DFS实现的代码示例(假设图的节点编号从0开始):
```
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int cur) {
visited[cur] = true;
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur][i];
if (!visited[next]) {
dfs(graph, visited, next);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n); // 图的邻接表表示
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<bool> visited(n, false); // 标记节点是否已经被访问过
int cnt = 0; // 连通分量的个数
for (int i = 0; i < n; i++) {
if (!visited[i]) {
cnt++;
dfs(graph, visited, i);
}
}
if (cnt == 1) {
cout << "Yes" << endl;
} else {
cout << cnt << endl;
}
return 0;
}
```
当然,也可以使用BFS来实现,方法类似。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)