Cube Stacking-蒲公英云

Cube Stacking

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 26409		Accepted: 9239
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

Sample Output

1
0
2

Source

USACO 2004 U S Open

题目大意：有N个立方体和N个格子，1~N编号，一開始i立方体在i号格子上，每一个格子刚好1个立方体。如今m组操作，M a b表示将a号立方体所在的格子的所有立方体放在b号立方体所在的格子的所有立方体上面。C x表示询问x号立方体以下的立方体的个数。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 30001
int p,fu[N],zi[N],juli[N];
int Make_set()//初始化并查集
{
    int i;
    for(i=1;i<N;i++)
    {
        fu[i]=i;//按题目要求对盒子进行编号
        zi[i]=1;
        juli[i]=0;
    }
}
int Find_Set(int x)//找祖宗
{
    int fx=fu[x];
    if(fu[x]!=x)
    {
        fx=Find_Set(fu[x]);
        juli[x]+=juli[fu[x]];
    }
    return fu[x]=fx;
}
void Union(int a,int b)//合并两个集合
{
    int x,y;
    x=Find_Set(a);
    y=Find_Set(b);
    if(x==y)//相等则在同一个集合中
        return ;
    fu[y]=x;
    juli[y]+=zi[x];
    zi[x]+=zi[y];
}
int main()
{
    while(scanf("%d",&p)!=EOF)
    {
        int i,j,a,b;
        char s[3];
        Make_set();
        for(i=1;i<=p;i++)
        {
            scanf("%s",s);
            if(s[0]=='C')
            {
                scanf("%d",&a);
                b=Find_Set(a);
                printf("%d\n",zi[b]-juli[a]-1);
            }
            else
            {
                scanf("%d%d",&a,&b);
                Union(a,b);
            }
        }
    }
    return 0;
}