1564.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1564 on 2006-03-19 at 09:31:52 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 32768;

class UFSet {
private:
	int parent[MAX];
public:
	void make();
	int find(int);
	void unionSet(int, int);
};
void UFSet::make() {
	memset(parent, -1, sizeof(parent));
}
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x), pY = find(y);
	if(pX != pY) parent[pX] = pY;
}

int main()
{
	UFSet ufs;
	int i, j, n, m;
	
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		ufs.make();
		for(i = 0; i < m; i++) {
			int gn, b; scanf("%d", &gn);
			for(j = 0; j < gn; j++) {
				int e; scanf("%d", &e);
				if(j != 0) ufs.unionSet(b, e);
				b = e;
			}
		}
		int sus = 0;
		for(i = 0; i < n; i++)
			if(ufs.find(0) == ufs.find(i)) sus++;
		printf("%d\n", sus);
	}
	
	return 0;
}