poj 1988 Cube Stacking(带权并查集)

题目链接：poj 1988 Cube Stacking

题目大意：给出n，表示有n个立方体，p次操作（p未给出）操作分两种，M a b 将a所在列的正方体整个移动至b所在的立方体上面，C a 计算在a下面有几个立方体。

解题思路：带权并查集，根为最底下的立方体，权值代表当前立方体下面有几个，然后在一个数组记录说每一列有多少个立方体，在和并两列的时候作为移动那列的权值。

#include <stdio.h>
#include <string.h>

const int N = 30005;

int n, f[N], s[N], v[N];

int getfar(int x) {
	if (x != f[x]) {
		int t = f[x];
		f[x] = getfar(f[x]);
		v[x] += v[t];
	}
	return f[x];
}

void init () {
	scanf ("%d", &n);
	for (int i = 0; i < N; i++) {
		f[i] = i;
		s[i] = 1;
	}
	memset(v, 0, sizeof(v));
}

int main () {
	init ();

	int a, b;
	char str[10];

	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		if (str[0] == ‘M‘) {
			scanf("%d%d", &a, &b);
			int p = getfar(a), q = getfar(b);
			if (p != q) {
				f[p] = q;
				v[p] = s[q];
				s[q] += s[p];
			}
		} else {
			scanf("%d", &a);
			int p = getfar(a);
			printf("%d\n", v[a]);
		}
	}
	return 0;
}

poj 1988 Cube Stacking(带权并查集),布布扣,bubuko.com

poj 1988 Cube Stacking(带权并查集)

原文：http://blog.csdn.net/keshuai19940722/article/details/23926001