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; }
原文:http://www.cnblogs.com/wuwangchuxin0924/p/6390093.html