girls and boys(二分图最大独立集).cpp

杭电acm解题报告2001---2099.

//Bi-partite Graph the maxinum indepented set = vertex number - maxinum match
#include<cstdio>
#include<memory>
#include<vector>
using namespace std;

const int Max = 510;
vector< vector<int> > Bmap;
int n, m, k, nm;
int mark[Max];
bool flag[Max];

bool dfs(int pos)
{
	int i, pre, tp;
	for(i=0; i < Bmap[pos].size() ;i++) {
		tp = Bmap[pos][i];
		if( !flag[tp] ) {
			flag[tp] = true;
			pre = mark[tp];
			mark[tp] = pos;
			if(pre==-1 || dfs(pre)) {
				return true;
			}
			mark[tp] = pre;
		}
	}
	return false;
}

inline int Max_Match()
{
	int mmax = 0, i;
	for(i=0; i < n ;i++) {
		memset(flag,0,sizeof(flag));
		if( dfs(i) ) {
			mmax++;
		}
	}
	return mmax / 2;
}

int main()
{
	int i, j, id1, id2;
	while(scanf("%d", &n)==1) {
		Bmap.clear();
		Bmap.resize(n+10);
		memset(mark,-1,sizeof(mark));

		for(i=0; i < n ;i++) {
			scanf("%d: (%d)", &id1, &m);
			for (j=0; j<m ;j++) {
				scanf("%d", &id2);
				Bmap[id1].push_back(id2);
			}
		}
		printf("%d\n", n - Max_Match());
	}
}