POJ 1988 Cube Stacking-CSDN博客

本文介绍了一道关于并查集的应用题，通过模拟Farmers John和Betsy的游戏过程，详细解析了如何使用并查集来高效解决该问题。文章提供了具体的实现代码，并解释了关键的数据结构和算法细节。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

Sample Output

1
0
2

题意：
第一行：输入P，代表接下来有P行输入
接下来P行，输入有两种情况即： 1：M x y 代表将x所在的一堆木块整体放在y所在的一堆木块上面 
 			      2：M x   代表求出x木块下面有多少木块
题解：知道这是一道带权并查集，但是怎么也想不到思路，并查集很抽象，会基础的并查集，但是很难推广，因为没有做过类似的题，很难想到这种思想，建议去做一下kuangbin的专题四，并查集训练一下！这道题我认为最主要的就是如果路径压缩，在这里我用getf（v)作为路径压缩也可以用作合并查找，用place[x]代表x下面有几个木块,用num[x]代表初始值，用于计算，这种方法是参考了一位大佬的思路，过几天要专门写一下并查集的题。
转载注明出处：http://blog.163.com/yc5_yc@126/blog/static/1388461592012367373485/
具体代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define maxn 30050
int f[maxn];
int num[maxn];
int place[maxn];
void init() {
	for(int i = 0 ; i < 30005; i++) {
		f[i] = -1;
		num[i] = 1;
		place[i] = 0;
	}
}
int getf(int v) {
	if(f[v] != -1) {
		int tmp = f[v];
		f[v] = getf(f[v]);
		place[v] += place[tmp];
		return f[v];
	}
	return v;
}
void merge(int v, int u) {
	int t1 = getf(v);
	int t2 = getf(u);
	if(t1 != t2) {
		f[t1] = t2;
		place[t1] += num[t2];
		num[t2] += num[t1];
	}
}
int main() {
	int P;
	int x, y;
	scanf("%d",&P);
	char op;
	init();
	while(P--) {
		cin >> op;
		if(op == 'M') {
			scanf("%d%d",&x,&y);
			merge(x, y);
		}
		else {
			scanf("%d",&x);
			getf(x);
			printf("%d\n",place[x]);
		}
	}
	return 0;
}