1988.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"

int set[30001];
int ans[30001];

int st[30000],sn;

int find_root( int s )
{
	int t;
	sn = 0;
	while( set[s] >=0 )
	{
		st[sn++] = s;
		s = set[s];

	}

	t = 0;

	while( sn-- )
	{
		set[ st[sn] ] = s;
		ans[ st[sn] ] +=t;
		t = ans[ st[sn] ];
	}

	return s;
}

void merge( int a, int b )
{
	int ra = find_root( a ), rb = find_root( b );

	ans[ra] = -set[rb];
	set[rb] += set[ra];
	set[ra] = rb;
}

int main()
{
	int p, a, b;
	char c[2];

	memset( set, -1, sizeof( set ) );
	memset( ans,  0, sizeof( ans ) );

	scanf( "%d", &p );

	while( p-- )
	{
		scanf( "%1s", c );
		if( c[0] == 'C' )
		{
			scanf( "%d", &a );
			find_root(a);
			printf( "%d\n", ans[a] );
		}
		else
		{
			scanf( "%d %d", &a, &b );
			merge( a, b );
		}
//		for(int i=0; i<8; i++ )
//			printf( "%d ", set[i] );
//		printf( "\n" );
	}

	return 0;
}