移动积木

初始有N堆积木，第i堆积木只有一个编号为i的积木，然后进行p次操作，每次操作可能为以下两种：

M x y：将编号x所在的那堆积木放到编号y所在的那堆积木的上面。

输入描述:

第一行一个整数q，表示操作次数。
接下来有q行输入，M, x, y或者C, x（保证）。
积木的总个数N，不会出现在输入中。初始时每个积木单独为一列。你可以认为，操作过程中，不会出现编号大于30000的积木。

输出描述:

对于每个询问，输出相应的值。

示例1
输入

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

输出

1
0
2

说明

1<=n<=30000，q<=10^5

yidongjimu.cppview raw

#include<iostream>
#include<stdio.h>
#define M 30005
using namespace std;
int m;
int p[M],dis[M];//cnt里为最终答案
int sz[M];
char S[5];
int find(int x) {
    if(p[x]!=x) {
        int t=find(p[x]);
        dis[x]+=dis[p[x]];
        p[x]=t;
        return t;
    }
    return x;
}
int main() {
    //a移至b上与b移至a下相同
    scanf("%d",&m);
    for(int i=1; i<=M-5; i++)p[i]=i,dis[i]=0,sz[i]=1;
    for(int i=1,x,y; i<=m; i++) {
        scanf("%s",S);
        if(S[0]=='M') {
            scanf("%d%d",&x,&y);
            int r1=find(x),r2=find(y);
            if(r1!=r2) {
                p[r1]=r2;
                dis[r1]+=sz[r2];
                sz[r2]+=sz[r1];
                sz[r1]=0;
            }
        } else {
            scanf("%d",&x);
            int r=find(x);
            printf("%d\n",dis[x]);
        }
    }
    return 0;
}