hdu1232 畅通工程

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn = 1000;
int f[maxn+10];

int getFather(int x) {
	if(x == f[x]) return x;
	else return f[x] = getFather(f[x]);
}

int gn, gm;
int main(void)
{
	int x, y;
	while(scanf("%d", &gn) == 1 && gn) {
        scanf("%d", &gm);
		for(int i = 1; i <= gn; i++) f[i] = i;
		for(int i = 0; i < gm; i++) {
			scanf("%d%d", &x, &y);
			int t1 = getFather(x);
			int t2 = getFather(y);
			if(t1 != t2) {
				f[t1] = t2;
			}
		}
		int cnt = 0;
		for(int i = 1; i <= gn; i++) {
			if(f[i] == i) cnt++;
		}
		printf("%d\n", cnt-1);
	}
	return 0;
}

hdu1232 畅通工程,布布扣,bubuko.com

hdu1232 畅通工程

原文：http://blog.csdn.net/achiberx/article/details/21509683