2385.cpp

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

/* This Code is Submitted by wywcgs for Problem 2385 on 2006-09-28 at 16:53:55 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int N = 32000;

class UFSet {
public:
	int parent[N], rank[N], cnt[N];
	void clear();
	pii find(int);
	void unionSet(int, int);
};
void UFSet::clear() {
	memset(parent, -1, sizeof(parent)); memset(rank, 0, sizeof(rank));
	for(int i = 0; i < N; i++) cnt[i] = 1;
}
pii UFSet::find(int x) {
	if(parent[x] == -1) return pii(x, 0);
	pii r = find(parent[x]);
	rank[x] += r.second; parent[x] = r.first;
	return pii(parent[x], rank[x]);
}
void UFSet::unionSet(int x, int y) {
	pii px = find(x), py = find(y);
	if(px.first == py.first) return;
	parent[py.first] = px.first; rank[py.first] = cnt[px.first]; cnt[px.first] += cnt[py.first];
}

int main()
{
	UFSet uf;
	int pn;
	
	while(scanf("%d %d", &pn) != EOF) {
		uf.clear();
		for(int i = 0; i < pn; i++) {
			char c; int x, y;
			scanf("\n%c", &c);
			switch(c) {
			case 'M': scanf("%d %d", &y, &x); uf.unionSet(x, y); break;
			case 'C': scanf("%d", &x); printf("%d\n", uf.find(x).second); break;
			}
		}
	}
	
	return 0;
}