Cube Stacking, 2004 Open
约翰和贝西在叠积木。共有30000块积木，编号为1到30000。一开始，这些积木放在地上，自然地分成N堆。贝西接受约翰的指示，把一些积木叠在另一些积木的上面。一旦两块积木相叠， 彼此就再也不会分开了，所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作，操作分为两种：
? 第一种是移动操作，格式为“移动X到Y的上面”。X和Y代表两块积木的编号，意思是将X所的那堆积木，整体叠放到Y所在的那堆积木之上；
? 第二种是统计操作，格式为“统计Z下方的积木数量”。Z代表一块积木的编号，意思是贝西需要报告在编号为Z的积木之下还有多少块积木
请编写一个程序，帮助贝西回答每条统计问题。
? 第一行：单个整数：P，1 ≤ P ≤ 10^5
? 第二行到第P + 1行：每行描述一条命令，如果这行开头的字母是 M，代表一条移动命令，后面的两个整数代表上文中的X和Y；如果开头字母是 C，代表一条统计命令。后面的整数代表上文中的Z，保证所有的移动命令都有意义，X和Y不会已经出现在同一堆积木里
? 对每一个统计命令，输出正确回答，用换行符分开每个查询的结果
6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4
1 0 2
第一次查询时， 1 下面只有一个 6；第二次查询时， 3 下面没有任何积木；第三次查询时，4 下面有两块积木：1 和 6
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int p,a,b,fa[100006],sum[100006],num[100006];
//fa[]就不说了，sum[]是来存它下面的积木数，num[]是这一列的积木数。
//比常规的并查集多了一行
char ch;
int read(){//快读
int a=0,b=1;
char ch=getchar();
while((ch<‘0‘||ch>‘9‘)&&(ch!=‘-‘)){
ch=getchar();
}
if(ch==‘-‘){
b=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘){
a=a*10+ch-‘0‘;
ch=getchar();
}
return a*b;
}
int get(int x){
if(x==fa[x]){
return x;
}
int hx=get(fa[x]);
sum[x]+=sum[fa[x]];//还需要统计它下面的积木数
return fa[x]=hx;
}
int main(){
p=read();
for(int i=1;i<=100006;i++){
fa[i]=i;//嗯，它的祖先就是它自己，常规操作
//sum[i] = 0;//它的下面肯定没有积木啊
num[i]=1;//目前这一列只有一个积木
}
while(p--){
ch=getchar();
while((ch<‘A‘)||(ch>‘Z‘)){
ch=getchar();
}
if(ch==‘M‘){
a=read(),b=read();
a=get(a),b=get(b);
if(a!=b){//如果他们的祖先不同，就是他们不在同一个联通块上
fa[a]=b;//合并它们
sum[a]=num[b];//数量要相加
num[b]+=num[a];//因为a要和b合并
}
}
if(ch==‘C‘){
a=read();
get(a);//还需要再来一次
printf("%d\n",sum[a]);
}
}
return 0;
}
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int p,a,b,fa[100006],sum[100006],num[100006];
char ch;
int read(){
int a=0,b=1;
char ch=getchar();
while((ch<‘0‘||ch>‘9‘)&&(ch!=‘-‘)){
ch=getchar();
}
if(ch==‘-‘){
b=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘){
a=a*10+ch-‘0‘;
ch=getchar();
}
return a*b;
}
int get(int x){
if(x==fa[x]){
return x;
}
int hx=get(fa[x]);
sum[x]+=sum[fa[x]];
return fa[x]=hx;
}
int main(){
p=read();
for(int i=1;i<=100006;i++){
fa[i]=i;
num[i]=1;
}
while(p--){
ch=getchar();
while((ch<‘A‘)||(ch>‘Z‘)){
ch=getchar();
}
if(ch==‘M‘){
a=read(),b=read();
a=get(a),b=get(b);
if(a!=b){
fa[a]=b;
sum[a]=num[b];
num[b]+=num[a];
}
}
if(ch==‘C‘){
a=read();
get(a);
printf("%d\n",sum[a]);
}
}
return 0;
}
原文：https://www.cnblogs.com/xiongchongwen/p/11839609.html