完整的c语言代码,实现测试数据有多组,第一行会给出一个整数N,N<20,表示这幅图节点的个数。然后会给出一个N阶的矩阵表示这个图,1表示连通,0表示两点间无路径,自己到自己的权值记做0.如果给出的图是一个连通图则输出"YES",否则输出"NO"
时间: 2023-11-02 09:04:53 浏览: 115
以下是实现上述功能的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 20
int graph[MAX_NODES][MAX_NODES];
int visited[MAX_NODES];
void dfs(int node, int n) {
visited[node] = 1;
for (int i = 0; i < n; i++) {
if (graph[node][i] && !visited[i]) {
dfs(i, n);
}
}
}
int is_connected(int n) {
dfs(0, n);
for (int i = 0; i < n; i++) {
if (!visited[i]) {
return 0;
}
}
return 1;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
if (is_connected(n)) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
```
该程序首先读取输入的节点数n和对应的图矩阵,然后使用深度优先搜索算法判断图是否连通。如果图连通,则输出"YES",否则输出"NO"。
阅读全文