POJ-1988 Cube Stacking (带权并查集)

输入输出格式：

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.

题意：给出一个编号范围为N（1 <= N <= 30,000）的箱子（N不会给出来），然后接下来有p次操作 ：

M x y 将含有元素x的栈放在含有y的栈的顶端，合并为一个栈: 　　

C x 询问含有x元素下面有多少个元素。

思路：在普通的并查集操作上增加一个记录权值的数组。在合并(unite)的同时进行权值修改.用cnt

完整代码：

#include<cstdio>
#include<cstring>const int maxn=1e5+10;
int n,m,k,t,pre[maxn],ret[maxn],cnt[maxn];
int find(int x)
{
    if(x==pre[x])return x;
    int y=pre[x];
    pre[x]=find(pre[x]);
    ret[x]+=ret[y];
    return pre[x];
}
void unite(int x,int y){
    x=find(x),y=find(y);
    pre[x]=y;
    ret[x]+=cnt[y];
    cnt[y]+=cnt[x];
}
int main()
{
    int i,j;
    char op[2];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
　　　　pre[i]=i,cnt[i]=1;
    for(i=1;i<=n;i++)
    {
        scanf("%s%d",op,&j);
        if(op[0]=='M')
        {
            scanf("%d",&k);
            unite(j,k);
        }
        else
        {
            find(j);
            printf("%d
",ret[j]);
        }
    }
    return 0;
}