1182.txt

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

#include <stdio.h>
#include <memory.h>

int s[50011];
int enemy[50011], food[50011];

int st[50011], sn;

int find( int k )
{
	int t = k;
	sn = 0;
	while( s[ k ] > 0 )
	{
		st[ sn++ ] = k;
		k = s[k];
	}
	
	while( sn-- )
		s[ st[sn] ] = k;



	return k;
}

int merge( int a, int b )
{
	int t;
	if( a != b && a && b )
	{
		if( s[a] > s[b] )
		{	t = a;	a = b;	b = t; }

		s[a] += s[b];
		s[b] = a;
	}
	return (a==0)?b:a;
}

int main()
{
	int n, m, i, j, d, k, h, ans, a, b, c;

	scanf( "%d %d", &n, &m);

	memset( s, -1, sizeof( int ) * ( n+1 ) );
	memset( enemy, 0, sizeof( int ) * ( n+1 ) );
	memset( food, 0, sizeof( int ) * ( n+1 ) );


	ans = 0;
	while( m-- )
	{

		scanf( "%d %d %d", &d, &i, &j );
		
		if( i > n || j > n || i == j && d == 2 )
		{	ans++; continue; }

		i = find( i );
		j = find( j );

		if( d == 1 )
		{
			if( ( k = find( enemy[i] ) ) && k == j || ( h = find( enemy[j] ) ) && h == i )
			{	ans++; continue; }
			else 
			{
				a = merge( i, j );
				food[i] = food[j] = b = merge( find( food[i] ), find( food[j] ) );
				enemy[i] = enemy[j] = c = merge( k, h );
			}
		}
		else
		{
			if( i == j || ( k = find( enemy[i] ) ) && k == j )
			{	ans++; continue; }
			else
			{
				food[j] = enemy[i] = a = merge( k, find( food[j] ) );
				enemy[j] = b = merge( i, find( enemy[j] ) );
				food[i] = c = merge( find( food[i] ), j );
			}
		}
		
		if( a && c ) enemy[a] = c;
		if( b && a ) enemy[b] = a;
		if( c && b ) enemy[c] = b;

		if( a && b ) food[a] = b;
		if( c && a ) food[c] = a;
		if( b && c ) food[b] = c;
	}

	printf( "%d\n", ans );

	return 0;
}