HDU 3635 并查集+路径压缩+记录每个点移动次数

题意:

给定n个点 oper个操作

每个点有1个龙珠

下面2种操作:

T u v 把u点所有龙珠搬到v

Q u  问u点当前所在城市 u点所在城市有几个龙珠 u点被移动几次

思路:

并查集可以求出 u 点所在城市,记录每个点的 son(子节点数)可以求出 某城市的龙珠数量

用step 记录每个点被移动了几次

#include<stdio.h>
#include<string.h> inline int Max(int a,int b){return a>b?a:b;}
#define N 100001
struct node{
int step, parent, son;
}a[N];
char s[2];
int find(int x){
if(x==a[x].parent)return x;
int temp = a[x].parent;
a[x].parent = find(a[x].parent);
a[x].step += a[temp].step;
return a[x].parent;
}
void Union(int x, int y){
int fx = find(x), fy = find(y);
if(fx == fy)return;
a[fx].parent = fy;
a[fx].step ++;
a[fy].son += a[fx].son;
a[fx].son = 0;
}
int main(){
int T, Cas = 1, n, oper, i, j, u, v; scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&oper);
printf("Case %d:\n", Cas++);
for(i = 1; i<= n; i++)
{
a[i].son = 1;
a[i].parent = i;
a[i].step = 0;
}
while(oper--){
scanf("%s",s);
if(s[0] == 'T')
{
scanf("%d %d",&u,&v);
Union(u, v);
}
else
{
scanf("%d",&u);
int ans = find(u);
printf("%d %d %d\n",ans, a[ ans ].son, a[u].step);
}
}
}
return 0;
}
上一篇:Leetcode 86


下一篇:【BZOJ】【4010】【HNOI2015】菜肴制作