POJ1988

思考：节点的表示，压缩路径时候更新。

#include <cstdio>
#include <iostream>

using namespace std;
const int maxn = 30001;
//Accepted	1044K	579MS	G++	829B	2014-03-23 09:13:48
int f[maxn+10];
int sum[maxn+10];
int up[maxn+10];

int getFather(int x) {
	if(x == f[x]) return x;
	int fa = f[x];
	f[x] = getFather(f[x]);
	up[x] += up[fa];
	return f[x];
}

void init() {
	for(int i = 1; i < maxn; i++) {
		f[i] = i;
		sum[i] = 1;
		up[i] = 0;
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	char str[5];
	int x, y;
	init();
	while(n--) {
		scanf("%s", str);
		if(str[0] == ‘M‘) {
			scanf("%d%d", &x, &y);
			int t1 = getFather(x);
			int t2 = getFather(y);
			if(t1 != t2) {
				f[t2] = t1;
				up[t2] = sum[t1];
				sum[t1] += sum[t2];
			}
		} else {
			scanf("%d", &x);
			int t1 = getFather(x);
			int res = sum[t1]-up[x]-1;
			printf("%d\n", res);
		}
	}
	return 0;
}

POJ1988,布布扣,bubuko.com

POJ1988

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