连通图 （C++代码）(并查集)

解题思路:
                判断连通图，构建并查集即可
注意事项:

参考代码:

#include <iostream>
#include <cstring>
using namespace std;
int arr[1050];
bool vis[1050];
int root(int x) {
	int r = x;
	while (arr[r] != r) { //寻找祖先
		r = arr[r];
	}
	int i = x, j;
	while (i != r) {	//路径压缩
		j = arr[i];
		arr[i] = r;
		i = j;
	}
	return r;
}
int main() {
	int n, m;
	while (cin >> n >> m && n && m) {
		for (int i = 1; i <= 1050; i++) //初始化
			arr[i] = i;
		memset(vis, 0, sizeof(vis));
		for (int i = 1; i <= m; i++) { 
			int a, b;
			cin >> a >> b;
			int fx = root(a);
			int fy = root(b);
			arr[fx] = fy;
		}
		for (int i = 1; i <= n; i++) {//标记祖先
			vis[root(i)] = 1;
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) { // 查找有多少个祖先，则连通图则有几个
			if (vis[i]) {
				ans++;
			}
		}
		if (ans == 1)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}