给定一个无向图和其中的所有边,判 断这个图是否所有顶点都是连通的。 Input 每组数据的第一行是两个整数 n 和 m (0<= n <=1000)。 n 表示图的顶点数目, m 表示图中边的数目。如果 n 为0表示输入结束。随后有 m 行数据,每行有两个值 x 和 y (0< x , y <= n ),表示顶点 x 和 y 相连,顶点的编号从1开始计算。输入不保证这些边是否重复。 Output 对于每组输入数据,如果所有顶点都是连通的,输出" YES ",否则输 出" NO "。 Sample Input : 4 3 4 3 1 2 1 3 5 7 3 5 2 3 1 3 3 2 2 5 3 4 4 1 7 3 6 2 3 1 5 6 0 0 Sample Output YES YES NO。用c语言实现代码
时间: 2024-02-23 18:02:57 浏览: 22
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 1005
int n, m;
int fa[MAXN]; // 并查集数组
void init() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) { // 并查集查找
if (fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int x, int y) { // 并查集合并
fa[find(x)] = find(y);
}
bool check() { // 判断是否所有顶点都是连通的
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] == i) {
cnt++;
if (cnt > 1) {
return false;
}
}
}
return true;
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
init();
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
merge(x, y);
}
if (check()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
```
算法思路:
使用并查集维护连通性。对于每一对相连的顶点,将它们所在的集合合并。如果最终只有一个集合,说明所有顶点都是连通的。否则,说明有不连通的顶点。