题解 | #连通图#

利用并查集实现，代码不难
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define N 1000  //元素的上限个数
int father[N]; //存储了每个元素父亲的下标
int height[N]; // 存储了某个根的高度

void Init(int n) {
	//最开始时，每个元素单独构建一个集合
	for (int i = 1; i <= n; i++) {
		father[i] = i;  //每个元素都是一个跟
		height[i] = 1;  //初始高度都为1
	}

}
int Find(int x) {
	if (x != father[x]) {
		//递归向上查找
		// find的路径压缩，找到祖先后不进行返回，而是设置成自己的父亲
		father[x] =  Find(father[x]);  // 把链表上所有节点的父亲都改为祖先
	}

	return father[x];
}
void Union(int x, int y,int & num) {
	//合并两棵树，合并y的祖先，把y的祖先的父亲设为x的祖先
	// father[Find(y)] = Find(x);
	x = Find(x); 
	y = Find(y);
	if (x != y) {         // x与y原本不属于同一个连通子图
		--num;  //减少连通子图的数量

	}
	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 m, n;
	while (cin >> n >> m) {
		if (m == 0 && n == 0) 
			break;
		Init(n);  //初始化并查集
		int num = n; //连通子图的数量
		for (int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			Union(x, y,num);
		}
		if (num == 1) {
			cout << "YES" << endl;
		}
		else cout << "NO" << endl;

	}

}