View Code of Problem 1010

#include <cstdio>
#include <cstring>
const int maxn = 550;
bool road[maxn][maxn],vis[maxn];
int point[maxn];
int n,m;
void init()
{
	int i,si,ei;
	memset(road,0,sizeof(road));
	memset(point,0,sizeof(point));
	for(i=0;i<m;++i)
	{
		scanf("%d%d",&si,&ei);
		road[si][ei] = true;
	}
}
void floyd()		//因为中间点可重复访问，则用floyd进行缩点,间接连通转为直接连通 
{
	int i,j,k;
	for(k=1;k<=n;++k)
	{
		for(i=1;i<=n;++i)
		{
			for(j=1;j<=n;++j)
			{
				if(road[i][k]+road[k][j]==2)
					road[i][j]=1;
			}
		}
	}
}
bool find(int p)		//再用匈牙利算法求最大匹配 
{
	int i;
	for(i=1;i<=n;++i)
	{
		if(road[p][i]==true&&!vis[i])
		{
			vis[i]=true;
			if(point[i]==0||find(point[i]))
			{
				point[i]=p;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	int i,count,ans;
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)	break;
		if(m==0)
		{
			printf("%d\n",n);
			continue;
		}
		init();
		floyd();
		count=0;
		for(i=1;i<=n;++i)
		{
			memset(vis,0,sizeof(vis));
			if(find(i))
				count++;
		}
		ans = n - count;		//最后求最小路径覆盖 
		printf("%d\n",ans);
	}
	return 0;
}