pku2594.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 510
int N, M;
int path[size][size];
int match[size];
int chk[size];

int DFS(int p)
{
	int i, t;
	for (i = 1; i <= N; i++)
	{
		if (path[i][p] && !chk[i])
		{
			chk[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[i] = t;
		}
	}
	return 0;
}

void Solve()
{
	int i, j, k, ans;
	int s, e;
	memset(path, 0, sizeof(path));
	for (i = 0; i < M; i++)
	{
		scanf("%d %d", &s, &e);
		path[s][e] = 1;
	}
	for (k = 0; k <= N; k++)
	{
		for (i = 0; i <= N; i++)
		{
			if (!path[i][k])
			{
				continue;
			}
			for (j = 0; j <= N; j++)
			{
				path[i][j] = path[i][j] || (path[i][k] && path[k][j]);
			}
		}
	}
	memset(match, -1, sizeof(match));
	for (i = 1, ans = 0; i <= N; i++)
	{
		memset(chk, 0, sizeof(chk));
		ans += DFS(i);
	}
	printf("%d\n", N - ans);
}
int main()
{
	while (scanf("%d %d", &N, &M) != -1 && (M + N))
	{
		Solve();
	}	
	return 0;
}