题解 | #畅通工程#

#include<cstdio>
using namespace std;

const int MAXN = 1000;

int father[MAXN];	//定义父节点数组 
int height[MAXN];	//结点高度数组

void Initial(int n) {
	for(int i = 0; i <= n; ++i) {
		father[i] = i;   		//每个结点的父节点是自己 
		height[i] = 0;			//高度都是0 
	}
} 

int Find(int x) {				//查找根节点 
	if (x != father[x]) {		//路径压缩 
		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[y] = x;
		} else if (height[y] > height[x]) {
			father[x] = y;
		} else {
			father[y] = x;
			height[x]++;
		}
	}
	return;
}

int main() {
	int n, m;
	while(scanf("%d", &n) != EOF) {	//输入城镇树 
		if(n == 0) {
			break;
		}
		scanf("%d", &m);	//输入街道数 
		Initial(n);			//初始化 
		while(m--) {
			int x, y;
			scanf("%d", &x);
			scanf("%d", &y);
			Union(x, y);	//合并集合 
		}
		int answer = -1;
		for(int i = 1; i <= n; ++i) {
			if(Find(i) == i) {
				answer++;
			}
		}
		printf("%d\n", answer);
	}
	return 0;
}