Posted on 2011-09-09 11:39
成幸毅 阅读(290)
评论(0) 编辑 收藏 引用
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10010;
int n,m;
int father[MAXN], rank[MAXN], a,b;
int depth[MAXN],t;
void make() 
{
for(int i = 1; i <= n; i++) {
father[i] = i;
rank[i] = 1;
depth[i] = 0;
}
}
int _find(int x) {
int h = x;
t = 0;
while(h != father[h]) {
t = t + depth[h];
h = father[h];
}
int y;
int tmp;
while(x != h) {
t -= depth[x];
depth[x] += t;
y = father[x];
father[x] = h;
x = y;
}
return h;
}
void _union(int a,int b) {
int x = _find(a);
int y = _find(b);
rank[y] += rank[x];
depth[x] = 1;
father[x] = y;
}
char type;
int main() {
int cas;
while(scanf("%d",&cas) != EOF) {
for(int acase = 1; acase <= cas; acase++){
scanf("%d%d",&n,&m);
printf("Case %d:\n",acase);//<<":"<<endl;
make();
for(int i = 0; i < m; i++) {
scanf("\n%c",&type);
if(type == 'T') {
scanf("%d%d",&a,&b);
_union(a,b);
}
else {
scanf("%d",&a);
int tmp = _find(a);
printf("%d %d %d\n",tmp,rank[tmp],depth[a]);
// cout<<tmp<<" "<<rank[tmp]<<" "<<depth[a]<<endl;;
}
}
}
}
//system("pause");
return 0;
}