pku1988.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>

int set[30001];
int sum[30001];
int btn[30001];

void pre()
{
	int i;
	for (i = 0; i < 30001; i++)
	{
		set[i] = 0;
		sum[i] = 1;
		btn[i] = 0;
	}
}

int get_id(int x)
{
	int root, last;

	if (set[x] == 0)
	{
		return x;
	}
	last = set[x];
	root = get_id(last);
	if (last != root)
	{
		set[x] = root;
		btn[x] += btn[last];
	}
	return root;
}

int main()
{
	int P, X, Y, cnt, r1, r2, i;
	char p;

	scanf("%d", &P);
	pre();
	getchar();
	
	while (P--)
	{
		scanf("%c", &p);
		
		if (p == 'M')
		{
			scanf("%d %d", &X, &Y);
			getchar();
			r1 = get_id(X);
			r2 = get_id(Y);
			set[r1] = r2;
			btn[r1] = sum[r2];
			sum[r2] += sum[r1];
		}
		else
		{
			scanf("%d", &X);
			getchar();
			get_id(X);
			cnt = btn[X];
			printf("%d\n", cnt);
		}
	}
	return 0;
}