并查集用的很巧妙
#include <stdio.h>
#include <string.h>
int parent[30010], count[30010];
void init()
{
memset(parent, -1, sizeof(parent));
memset(count, 0, sizeof(count));
}
int find(int i)
{
if ( 0 > parent[i] )
return i;
int t= parent[i];
parent[i]= find(parent[i]);
count[i]+=count[t];
return parent[i];
}
void unionset(int a, int b)
{
a= find(a);
b= find(b);
if ( a == b ) return;
int t= parent[a];
parent[a]= b;
count[a]= count[a]-parent[b];
parent[b]+=t;
}
int main()
{
int n, a, b;
char ch;
scanf("%d", &n);
init();
while ( n-- )
{
scanf("%*c%c", &ch);
if ( 'M' == ch )
{
scanf("%d%d", &a, &b);
unionset(a, b);
}
if ( 'C' == ch )
{
scanf("%d", &a);
find(a);
printf("%d\n", count[a]);
}
}
return 0;
}