题解 | #连通图#

//土尔逊Torson 编写于2023/06/16
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN12701 = 1000;

int father12701[MAXN12701];      //父亲结点
int height12701[MAXN12701];      //结点高度

void Initial12701(int n) {               //初始化
	for (int i = 0; i <= n; i++) {
		father12701[i] = i;              //每个结点的父亲为自己
		height12701[i] = 0;              //每个结点的高度为零
	}
}

int Find12701(int x) {                   //查找根结点
	if (x != father12701[x]) {           //路径压缩
		father12701[x] = Find12701(father12701[x]);
	}
	return father12701[x];
}

void Union12701(int x, int y) {
	x = Find12701(x);
	y = Find12701(y);
	if (x != y) {
		if (height12701[x] < height12701[y]) {
			father12701[x] = y;
		}
		else if (height12701[y] < height12701[x]) {
			father12701[y] = x;
		}
		else {
			father12701[y] = x;
			height12701[x]++;
		}
	}
	return;
}

int main() {
	int n, m;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		scanf("%d", &m);
		Initial12701(n);                  //初始化
		while (m--) {
			int x, y;
			scanf("%d", &x);
			scanf("%d", &y);
			Union12701(x, y);             //合并集合
		}
		int component = 0;           //连通分量
		for (int i = 1; i <= n; i++) {
			if (Find12701(i) == i) {      //集合数目
				component++;
			}
		}
		if (component == 1) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")