首页 > 其他 > 详细

Building Block

时间:2017-02-11 22:43:53      阅读:180      评论:0      收藏:0      [点我收藏+]

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[300010];
int under[300010];//表示以i为根节点的数有多少木块(也就是i节点一下有多少木块)
int Rank[300010];//表示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[2];
int x,y;
void init(){
    for(int i=0;i<300005;i++){
        bin[i]=i;
        Rank[i]=1;
        under[i]=0;
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){    
        init();    
        while(n--){
            scanf("%s",op);
            if(op[0]==M){
                scanf("%d%d",&x,&y);
                merge(x,y);
            }else{//查找x这棵树有多少木块
                scanf("%d",&x);
                findx(x);
                printf("%d\n",under[x]);
            }
        }
    }
    return 0;
}

 

Building Block

原文:http://www.cnblogs.com/wuwangchuxin0924/p/6390093.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!