#POJ 1988 Cube Stacking (并查集 + 路径压缩变体)

Cube Stacking

Time Limit: 2000MS	Memory Limit: 30000K
Total Submissions: 30214	Accepted: 10621
Case Time Limit: 1000MS

Description

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:

moves and counts.

* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.

* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output

Print the output from each of the count operations in the same order as the input file.

Sample Input

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
           

Sample Output

1
0
2
           

题目大意 ： 有N个砖块一开始放在地上， 进行M次操作， 操作1将包含砖块 X 的那一摞砖块放到包含 Y的那一摞砖块上， 操作2输出某个砖块下面有多少个砖块

思路 ： 个人觉得比较好的一道题， 可以加深你对并查集还有路径压缩的理解。 这道题除了维护父亲之外， 还维护两个变量， 一个是孩子数量， 一个是高度， 不妨设最下面的砖块为每摞的父亲， 每当新合并两摞砖块时， 总是先将他们各自的父亲进行合并， 合并完之后， 上面的父亲的高度更新为下面父亲的孩子数量， 他本身的孩子数量不变， 下面父亲的高度不变， 孩子数量加上上面父亲的孩子数量， 这是并操作的修改内容， 而查操作时， 我们要对每一个砖块进行路径压缩， 否则无法更新所有的砖块， 每次先将该砖块的父亲节点给表示出来 （不一定在最底层， 指的合并时的父亲）， 然后从最下面的父亲开始往上更新， 每个结点的孩子数量不变， 高度加上刚刚表示出来的他未压缩路径之前的父亲的高度（此时他父亲的高度已经更新完了）， 注意每次输出时要再压缩一下路径

Accepted code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & (-x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

int p[MAXN], hei[MAXN], son[MAXN];
int n;
char op[5];
void init() {
	for (int i = 1; i <= n; i++) p[i] = i, son[i] = 1;
}
int find_(int x) {
	if (x == p[x]) return x; // 到底 
	int fa = p[x];   // 父亲表示出来
	p[x] = find_(p[x]);
	hei[x] += hei[fa];  // 父亲更新完， 加上他的高度
	return p[x];
}
void unite(int x, int y) {
	x = find_(x);
	y = find_(y);
	if (x != y) {
		p[x] = y;
		hei[x] = son[y];  // 更新节点
		son[y] += son[x];
	}
}

int main()
{
	cin >> n; init();
	for (int i = 0; i < n; i++) {
		int ui, vi;
		sc("%s", op);
		if (op[0] == 'M') {
			sc("%d %d", &ui, &vi);
			unite(ui, vi);
		}
		else {
			sc("%d", &ui);
			find_(ui);  // 再次路径压缩
			cout << hei[ui] << endl;
		}
	}
	return 0;
}