有标号为1到n的n个龙珠,分别放在对应标号为1到n的n个城市里。
下面有两种操作:
T A B表示把A龙珠所在城市的所有龙珠都转移到B龙珠所在的城市中
Q A 表示查询A,需要知道A龙珠现在所在的城市,A所在的城市有几颗龙珠,A转移到这个城市移动了多少次,分别输出3个整数,表示上述信息。
前两个用普通并查集就能算出来,移动次数不好维护;
如果我们不进行路径压缩,那么查询点的深度即是移动的次数,因为每移动一次父节点就下降一层,深度+1;
但不路径压缩的话就会超时,所以我们要把点的深度记录下来;;
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int ans[100000] ,ansn[100000] ,pre[100000];
void init( int x){
for( int i = 0 ; i<=x ;i++){
pre[i] = i;
ans[i] = 0;
ansn[i] = 1;
}
}
int find( int a){
/* int r=a; //刚开始这样记录深度ans[a],但是这样不对,这样只是路径压缩一次ans[n]++,但实际上一次可能压缩很多层,所以应该是加上上一层的压缩层数
while( pre[a]!=a){
a=pre[a];
}
int t;
while( pre[r]!=a){
ans[r]++;
t= pre[r];
pre[r] =a;
r=t;
}*/
if( a == pre[a] )return a;
else{
int tmp= pre[a];
pre[a] = find( pre[a]);
ans[a] += ans[tmp];
}
return pre[a];
}
int add( int a ,int b){
int x=find(a);
int y=find(b);
if( x != y){
pre[x] = y;
ans[x] = 1;
ansn[y] += ansn[x];
ansn[x] =0;
}
}
int main( ){
int ks=0, T;
scanf("%d",&T);
while( T--){
printf("Case %d:\n",++ks);
int n,m;
scanf("%d%d" ,&n ,&m);
init( n);
while( m--){
char op[10];
int a,b;
scanf("%s",op);
if( op[0] == 'T'){
scanf("%d%d" ,&a,&b);
add( a,b);
}
if( op[0] == 'Q'){
scanf("%d" ,&a);
int b=find(a);
printf("%d %d %d\n" ,b ,ansn[b] ,ans[a]);
}
}
}
return 0;
}