图论专题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 ;
}

 

上一篇:openwrt uci


下一篇:35.QT-多线程