【北大夏令营笔记-并查集】poj1988-Cube Stacking

Cube Stacking
Time Limit: 2000MS Memory Limit: 30000K
Total Submissions: 18401 Accepted: 6378
Case Time Limit: 1000MS
Description

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations: 
moves and counts. 
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y. 
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value. 

Write a program that can verify the results of the game. 
Input

* Line 1: A single integer, P 

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For
count operations, the line also contains a single integer: X. 

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself. 
Output

Print the output from each of the count operations in the same order as the input file. 
Sample Input

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output

1
0
2
Source

USACO 2004 U S Open

并查集的应用
将每一堆当成一个集合，当这一堆压倒那一堆的时候，进行集合合并

AC代码：

#include<stdio.h>
#include<stdlib.h>
#define MAX 31000
int parent[MAX];
int sum[MAX];
int under[MAX];
int GetRoot(int a)
{
    if(parent[a]==a)
    return a;
    int t=GetRoot(parent[a]);
    under[a]+=under[parent[a]];
    parent[a]=t;
    return parent[a];
}
void merge(int a,int b)
{
  //把b所在的堆，叠放到a所在的堆
  a=GetRoot(a);
  b=GetRoot(b);
  if(a==b)
  return;
  parent[b]=a;
  under[b]=sum[a];//under[b]赋值前一定是0，因为
  //parent[b]=b,b一定是原b所在堆的最底下的
  sum[a]+=sum[b];
}
int main()
{
    int i,j,n;
    for(i=0;i<MAX;i++)
    {
       sum[i]=1;
       parent[i]=i;
       under[i]=0;
    }
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        char s[20];
        int a,b;
        scanf("%s",s);
        if(s[0]=='M'){
              scanf("%d %d",&a,&b);
              merge(b,a);
        }else
        {
            scanf("%d",&a);
            GetRoot(a);//进行矩阵压缩，更新以前没有更新的under值(加上父亲以及所有祖先的under值)
            //最下面的那个是老祖宗，一般下面被压的的辈分比上面高
            printf("%d\n",under[a]);
        }
    }
    return 0;
}