hdu 2818--Building Block

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   这题算是一个简单的带权并查集的应用，问题中包含了两种操作，M操作，将包含x的block全部移到y上去，C操作询问在x下的block数是多少 如果直接存储x下的block数会很麻烦，我们还不如求x上面的blocks总数，最后用它父节点所有的子节点数-x上面的blocks数-x本身就得到了 要求的。对于带权并查集的应用，表示才刚开始学，所了解的也只有简单的几种。貌似这题跟黑书上的那个差不多。。 View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N=30010; 6 int father[N],rank[N],cnt[N]; 7 void init() 8 { 9 for(int i=0;i<=N-10;i++) 10 { 11 father[i]=i; 12 rank[i]=1; 13 cnt[i]=0; 14 } 15 } 16 int find(int x) 17 { 18 if(x==father[x]) 19 return x; 20 int t=father[x]; 21 father[x]=find(father[x]); 22 cnt[x]+=cnt[t]; 23 return father[x]; 24 } 25 void merge(int x,int y) 26 { 27 x=find(x),y=find(y); 28 if(x==y) 29 return ; 30 father[y]=x; 31 cnt[y]=rank[x]; 32 rank[x]+=rank[y]; 33 } 34 int main() 35 { 36 int p,u,v; 37 char cmd[2]; 38 while(scanf("%d",&p)!=EOF) 39 { 40 init(); 41 while(p--) 42 { 43 scanf("%s",cmd); 44 if(cmd[0]=='M') 45 { 46 scanf("%d%d",&u,&v); 47 merge(u,v); 48 } 49 else 50 { 51 scanf("%d",&u); 52 v=find(u); 53 printf("%d\n",rank[v]-cnt[u]-1); 54 } 55 } 56 } 57 return 0; 58 }

 

 

转载于:https://www.cnblogs.com/wilsonjuxta/archive/2013/04/03/2997209.html

相关资源：JAVA上百实例源码以及开源项目