pku1988 Cube Stacking


#include<stdio.h>

const int MAX=30005;
struct Tree
{
    int parent,deep;
};
Tree pre[MAX];

void initial()
{
    for(int i=1;i<MAX;i++)
    {
        pre[i].parent=-1;    //若为正值则记录父件，若为负值则记录集合元素的个数，包括树根

        pre[i].deep=0;        //记录到根节点的距离,必须规定树根的深度为0

    }
}

int find(int x)
{
    if(pre[x].parent<0) return x;
    int temp=pre[x].parent;
    pre[x].parent=find(pre[x].parent);
    pre[x].deep+=pre[temp].deep; //若树根的深度非0，则在重复查找树根时执行此句会造成子结点的深度的累加而出错                                                                

    return pre[x].parent;
}

void move(int x1,int x2)
{
    int r1=find(x1);
    int r2=find(x2);
    
    if(r1==r2) return ;
    pre[r2].deep=-pre[r1].parent;
    pre[r1].parent+=pre[r2].parent;
    pre[r2].parent=r1;
}

int main()
{
    int p;
    scanf("%d",&p);
    initial();
    char str[2];
    for(int i=0;i<p;i++)
    {
        scanf("%s",str);
        if(str[0]=='M')
        {
            int x1,x2;
            scanf("%d%d",&x1,&x2);
            move(x1,x2);
        }
        else
        {
            int x;
            scanf("%d",&x);
            int root=find(x);
            printf("%d\n",-pre[root].parent-pre[x].deep-1);
        }
    }
    return 0;
}

总结：

并查集的一般用法。