Building Block

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. C X : Count the number of blocks under block X 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 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4

Sample Output 1 0 2

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 ;
}