2414279_ac_359ms_1044k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int n, m;
int map[501][501];
int link[501], b[501];

int dfs(int v)
{
	int i;

	for(i = 1; i <= n; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(link[i]==0||dfs(link[i]))
			{
				link[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

void floyd()
{
	int i, j, m;

	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
			if(map[j][i])
				for(m = 1; m <= n; m++)
					if(map[i][m])
						map[j][m]=1;
	}
}


int main()
{
	int i;
	int a, s, ans;

	while(scanf("%d%d",&n,&m)==2)
	{
		if(n==0&&m==0)
			break;
		ans = 0;
		memset(map,0,sizeof(map));
		memset(link,0,sizeof(link));
		for(i = 0; i < m; i++)
		{
			scanf("%d%d",&a,&s);
			map[a][s] = 1;
		}
		floyd();
		for(i = 1; i <= n; i++)
		{
			memset(b,0,sizeof(b));
			ans += dfs(i);
		}
		printf("%d\n",n-ans);
	}
	return 1;
}