4681539_ac_79ms_532k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 44 行

#include<iostream>
using namespace std;
bool map[505][505];
bool used[505];
int match[505];
int n,m;
bool find(int count)
{
	for(int i=1;i<=n;i++)
	{
		if(map[count][i]&&!used[i])
		{
			used[i]=true;
			int t;
			t=match[i];
			match[i]=count;
			if(t==-1||find(t))return true;
			match[i]=t;
		}
	}
	return false;
}
int main()
{
	while(cin>>n>>m)
	{
		int x,y;
		memset(map,false,sizeof(map));
		for(int count=1;count<=m;count++)
		{
			cin>>x>>y;
			map[x][y]=true;
		}
		int result=0;
		memset(match,-1,sizeof(match));
		for(int i=1;i<=n;i++)
		{
			memset(used,false,sizeof(used));
			if(find(i)) result++;
		}
		cout<<result<<endl;
	}
	return 0;
}