2033.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2033 on 2005-09-27 at 16:25:41 */ 
#include <cstdio>
#include <cstring>
#define  MAX  50000

class UFSet {
public:
	long father[MAX+1];
	void makeSet() {
		long i;
		for(i = 0; i < MAX+1; i++) {
			father[i] = -1;
		}
	}
	long findFather(long x) {
		if(father[x] == -1) {
			return x;
		} else {
			return findFather(father[x]);
		}
	}
	void unionSet(long x, long y) {
		long fatherX = findFather(x);
		long fatherY = findFather(y);
		if(fatherX != fatherY) {
			father[fatherX] = fatherY;
		}
	}
};

int main()
{
	UFSet *student = new UFSet;
	long n, m, i, a, b, num, test = 1, f;
	bool visited[MAX+1];
	
	while(scanf("%ld %ld", &n, &m) == 2) {
		if(m == 0 && n == 0) {
			return 0;
		} else {
			memset(visited, false, sizeof(visited));
			student->makeSet();
			for(i = 0; i < m; i++) {
				scanf("%ld %ld", &a, &b);
				student->unionSet(a, b);
			}
			num = 0;
			for(i = 1; i <= n; i++) {
				f = student->findFather(i);
				if(f == -1) {
					num++;
				} else {
					if(!visited[f]) {
						visited[f] = true;
						num++;
					}
				}
			}
			printf("Case %ld: %ld\n", test, num);
			test++;
		}
	}
	
	return 0;
}