1930.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1930 on 2005-10-04 at 11:27:15 */ 
#include <cstdio>
#include <cstring>
#define  MAX  128

class Person {
public:
	bool heard[MAX+1];
	void init() {
		memset(heard, false, sizeof(heard));
	}
};

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

int main()
{
	UFSet *uf = new UFSet;
	Person *person[MAX+1];
	int P, T, opinion, f;
	int i, j, k, a, t;
	bool same, father[MAX+1];
	
	for(i = 0; i <= MAX; i++) {
		person[i] = new Person;
	}
	while(scanf("%d %d", &P, &T) == 2) {
		for(i = 1; i <= P; i++) {
			person[i]->init();
		}
		uf->makeSet();
		while(true) {
			scanf("%d", &a);
			if(a == -1) {
				break;
			} else {
				scanf("%d", &t);
				person[a]->heard[t] = true;
			}
		}
		for(i = 1; i <= P; i++) {
			for(j = i+1; j <= P; j++) {
				same = true;
				for(k = 1; k <= T; k++) {
					if(person[i]->heard[k] != person[j]->heard[k]) {
						same = false;
						break;
					}
				}
				if(same) {
					uf->unionSet(i, j);
				}
			}
		}
		memset(father, false, sizeof(father));
		opinion = 0;
		for(i = 1; i <= P; i++) {
			f = uf->findFather(i);
			if(!father[f]) {
				opinion++;
				father[f] = true;
			}
		}
		printf("%d\n", opinion);
	}
	
	return 0;
}