1422.txt

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

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

bool e[120][120];
int son[120], n;

bool sign1[120];
bool sign2[120];
bool flag[120];

bool search( int a )
{
	int i;

	sign1[a] = true;

	for( i=0; i<n; i++ )
	if( !sign2[i] && e[i][a] )
	{
		sign2[i] = true;
		if( son[i] == -1 || ( !sign1[son[i]] && search( son[i] ) ) )
		{
			son[i] = a;
			flag[a] = true;
			return true;
		}
	}

	return false;
}

int main( )
{
	int cas, m, i, j;

	scanf( "%d", &cas );

	while( cas-- )
	{
		scanf( "%d%d", &n, &m );
		memset( e, 0, sizeof e );

		while( m-- )
		{
			scanf( "%d%d", &i, &j );
			e[i-1][j-1] = true;
		}

		memset( flag, 0, sizeof flag );
		memset( son, -1, sizeof son );

		for( i=0; i<n; i++ )
		if( !flag[i] )
		{
			memset( sign1, 0, sizeof sign1 );
			memset( sign2, 0, sizeof sign2 );
			search( i );
		}

		int ans = 0;
		for( i=0; i<n; i++ )
			if( son[i] == -1 )ans++;

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

	return 0;
}