二分図poj 1274(ハンガリーアルゴリズム)


#include <iostream>
using namespace std;

const int POINT_NUM = 205;
int map[POINT_NUM][POINT_NUM];
bool visit[POINT_NUM];
int match[POINT_NUM];
int n, m;

bool path(int start)
{
	int i;
	
	for(i = 1; i <= m; i++)
	{
		if(map[start][i] && !visit[i])
		{
			visit[i] = true;
			if(match[i] == -1 || path(match[i]))
			{
				match[i] = start;
				return true;
			}
		}
		
	}
	return false;
}
int main()
{
	int i, j, sN, s;
	int result;
	
	while(scanf("%d%d", &n, &m) != EOF)
	{
		memset(match, -1, sizeof(match));
		memset(map, 0, sizeof(map));
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &sN);
			for(j = 1; j <= sN; j++)
			{
				scanf("%d", &s);
				map[i][s] = 1;
			}
		}
		result = 0;
		for(i = 1; i <= n; i++)
		{
			memset(visit, false, sizeof(visit));
			if(path(i))
				result++;
		}
		printf("%d
", result); } return 0; }