Building Block |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 156 Accepted Submission(s): 70 |
|
Problem Description
John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1...N。Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:
M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command. You are request to find out the output for each C operation. |
|
Input
The first line contains integer P. Then P lines follow, each of which contain an operation describe above.
|
|
Output
Output the count for each C operations in one line.
|
|
Sample Input
6 |
|
Sample Output
1 |
|
Source
2009 Multi-University Training Contest 1 - Host by TJU
|
|
Recommend
gaojie
|
/*
题意：两种操作：
M X Y : 将x所在的木块堆上的所有木块转移到y所在的木块堆
C X : 查询x所在的木块堆x下方的木块的数量 初步思路：很明显并查集 #错误：T了一发，没有压缩路径,wa了一发，压缩路径写惨了
*/
#include<bits/stdc++.h>
using namespace std;
int bin[];
int under[];//表示以i为根节点的数有多少木块(也就是i节点一下有多少木块)
int Rank[];//表示i节点所在的集合的木块数量
int findx(int x){
if(x!=bin[x]){
int tmp=findx(bin[x]);
under[x]+=under[bin[x]];
bin[x]=tmp;
}
return bin[x];
}
void merge(int x,int y){
int fx=findx(x);
int fy=findx(y);
if(fx!=fy){
bin[fx]=fy;//将x放到y节点上面
under[fx]+=Rank[fy];//x节点下面增加的肯定是y节点所在的全部木块
Rank[fy]+=Rank[fx];
}
}
int n;
char op[];
int x,y;
void init(){
for(int i=;i<;i++){
bin[i]=i;
Rank[i]=;
under[i]=;
}
}
int main(){
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
init();
while(n--){
scanf("%s",op);
if(op[]=='M'){
scanf("%d%d",&x,&y);
merge(x,y);
}else{//查找x这棵树有多少木块
scanf("%d",&x);
findx(x);
printf("%d\n",under[x]);
}
}
}
return ;
}