图论专题1考试Problem1

Problem 1. bricks
Input file: bricks.in
Output file: bricks.out
Time limit: 1 second
jyb 在BUAA 天天被大神虐，所以只能去搬砖了。
终于在2019 年的夏天，菜菜的jyb 找不到工作，真的去工地搬砖了。jyb 的工头cky 是一个很麻烦的人，他
会让jyb 按某种方式搬砖，还问会问一些奇怪的问题。
现在有n 块砖，m 次操作。操作有两种：
1. M x y 把编号为x 的砖所在的一摞砖搬到编号为y 的砖所在的一摞砖的上面。如果x 和y 在同一摞砖则
忽略这个操作。（最初，每块砖都是单独一摞）
2. C x 询问x 下面压着多少块砖。
jyb 搬砖实在是太累了，想请你帮忙回答一下cky 工头的询问。
Input
第1 行，2 个整数n;m，表示一共有多少块砖以及有多少操作。
接下来m 行，每行一个操作，操作表示形式与前文一致。
Output
对于每次询问操作，输出答案

bricks.in

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

bricks.out

1
0
2

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int father[maxn];

int n,m;

char opt[maxn];

int size[maxn];

int down[maxn],up[maxn];

int x,y;

int get(int x)

{

    int t;

    if(father[x]!=x)

    {

        t=father[x];

        father[x]=get(father[x]);

        up[x]+=up[t];

    }

    return father[x];

}

void merge(int x,int y)

{

    x=get(x);

    y=get(y);

    if(x!=y)

    {

        father[y]=x;

        up[y]=down[x];

        down[x]+=down[y];

    }

}

int main()

{

    freopen("bricks.in","r",stdin);

    freopen("bricks.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        father[i]=i;

        down[i]=;

        up[i]=;

    }

    for(int i=;i<=m;i++)

    {

        scanf("%s",opt);

        if(opt[]=='C')

        {

            scanf("%d",&x);

            printf("%d\n",down[get(x)]-up[x]-);

        }

        else

        {

            scanf("%d%d",&x,&y);

            merge(x,y);

        }

    }

    return ;

}

图论专题1考试Problem1的相关教程结束。