题记(3)--连通图的判断

目录

一、题目内容

二、输入描述

三、输出描述

四、输入输出示例

五、完整C语言代码

一、题目内容

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

二、输入描述

每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

三、输出描述

?对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

四、输入输出示例

输入：

4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0

输出：

NO
YES

五、完整C语言代码

AC代码~

#include <stdio.h>
#define N 2000
int height[N];
int father[N];
void init(int n){ // 初始化 
	for(int i=1;i<=n;i++){
		height[i] = 1;
		father[i] = i;
	}
}

int Find(int x){
	if(x!=father[x]){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x,int y){ //num即连通分量个数 
	int fx = Find(x);
	int fy = Find(y);
	if(height[fx] < height[fy]){
		father[fx] = fy;   
	}
	else if(height[fx] > height[fy]){
		father[fy] = fx;
	}
	else{
		father[fy] = fx;
		height[fx]++;
	}
}

int main(){
	
	int n,m;
	int a,b;
	while(scanf("%d%d",&n,&m)!=EOF){
		if(m == 0 && n == 0)
			break;
		init(n);
		int num = n;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&a,&b);
			if(Find(a)!=Find(b)){
				num--;
				Union(a,b);
			} 
		}
		if(num == 1)
			printf("YES\n");
		else{
			printf("NO\n");
		}
	}
	return 0;
}