View Code of Problem 1010

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

const int maxn=505;

int mat[maxn][maxn];
int mark[maxn];
bool used[maxn];
int n;

void floyd()
{
	for(int k=1;k<=n;k++)
	  for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	      mat[i][j]=mat[i][j]||(mat[i][k]&&mat[k][j]);
}

bool dfs(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(mat[x][i] && !used[i])
		{
			used[i]=1;
			if(mark[i]==-1 || dfs(mark[i]))
			{
				mark[i]=x;
				return true;
			}
		}
	}
	return false;
}

int hungary()
{
	memset(mark,-1,sizeof(mark));
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memset(used,0,sizeof(used));
		if(dfs(i))
		  ans++;
	}
	return ans;
}

int main()
{
	int m;
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0 &&m==0)
		  break;
		int x,y;
		memset(mat,0,sizeof(mat));
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			mat[x][y]=1;
		}
		floyd();
		/*for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		    if(mat[i][j])
		      printf("%d--%d\n",i,j);*/
		printf("%d\n",n-hungary());
	}
	return 0;
}