题解 | #连通图#

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = 1000;

int father[MAXN];

int height[MAXN];

void Initial(int n) {   //n个节点
	for(int i = 0; i <= n; ++i) {   //初始状态下，每个节点的父节点是其自身
		father[i] = i;
		height[i] = 0;
	}
	return;
}


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


void Union(int x,int y) {
	x = Find(x);
	y = Find(y);
	if(x != y) {
		if(height[x] < height[y]) {
			father[x] = y;
		} else if(height[x] > height[y]) {
			father[y] = x;
		} else {
			father[y] = x;
			height[x]++;
		}
	}
}



int main() {
	int n;   //顶点数
	int m;   //边数
	while(scanf("%d%d",&n,&m) != EOF) {
		if(n == 0) {
			break;
		}
		Initial(n);
		while(m--) {  //输入m条边，每条边由两个顶点表示
			int x;
			int y;
			scanf("%d%d",&x,&y);
			Union(x,y);   //合并
		}
		int count = 0;
		for(int i = 1; i <= n; ++i){
			if(i == Find(i)){   //是根节点
				count++;
			}
		}
		if(count == 1){   //表示是连通的
			printf("YES\n");
		}else{     //非连通
			printf("NO\n");
		}
	}
	return 0;
}