学步园

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=34236#problem/D

无力吐槽，少了memset这个头文件，居然判断的是TLE。。。

题意：给你N个标记了的点，从1~N代表第几颗龙珠，但是龙珠会移动到不同的城市，执行的命令中T代表移动，现在要求的就是Q查询第i颗龙珠目前所在的城市的编号，并且输出该城市目前总的龙珠个数，还有第i颗龙珠移动到该城市的次数；

解析：裸并查集，使用数组Move存储移动的次数，sum统计目前的龙珠数目；

// d.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <cstring>>
using namespace std;

const int maxn = 10005;
int fa[ maxn ], Move[ maxn ], sum[ maxn ];

void Start(){
	memset( Move, 0, sizeof( Move ) );
	for( int i = 0; i < maxn; ++i ){
		fa[ i ] = i;
		sum[ i ] = 1;
	}
}

int find( int x ){
	if( x == fa[ x ] )
		return x;
	int temp = find( fa[ x ] );
	Move[ x ] += Move[ fa[ x ] ];
	return fa[ x ] = temp;
}

void Union( int a, int b ){
	int x = find( a );
	int y = find( b );
	//if( x != y )
	{
		sum[ y ] += sum[ x ];
		Move[ x ]++;
		fa[ x ] = y;
	}
}

//int _tmain(int argc, _TCHAR* argv[])
int main()
{
	int Case, n, m, a, b;
	char ch;
	cin >> Case;
	for( int i = 1; i <= Case; ++i ){
		printf( "Case %d:\n", i );
		Start();
		cin >> n >> m;
		while( m-- ){
			cin >> ch;
			if( ch == 'T' ){
				cin >> a >> b;
				Union( a,  b );
			}
			else{
				cin >> a;
				int temp = find( a );
				printf( "%d %d %d\n", temp, sum[ temp ], Move[ a ] );
			}
		}
	}
	return 0;
}