poj 3041 Asteroids(二分图 *【矩阵实现】【最小点覆盖==最大匹配数】)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#define N 500+20
#define INF 0x3f3f3f3f

using namespace std;
int n, m;
int map[N][N];
int link[N];
bool vis[N];

bool match( int u )
{
	for(int i=1; i<=n; i++)
	{
		if(vis[i]==false && map[u][i]==1 )
		{
			vis[i]=true;
			if(link[i]==-1 || match(link[i]) )
			{
				link[i]=u;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i, j, k;
	int u, v;
	scanf("%d %d", &n, &m);
	memset(map, 0, sizeof(map));

	for(i=0; i<m; i++ ){
		scanf("%d %d", &u, &v);
		map[u][v] = 1;
	}
	memset(link, -1, sizeof(link));
	int ans=0;

	for(int i=1; i<=n; i++)
	{
		memset(vis, false, sizeof(vis));
        if(match(i))
            ans++;

	}
	printf("%d\n", ans );
	return 0;
}