POJ 1466 Girls and Boys(二分图最大独立集)

7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0

5
2

 题意：

有n个学生，并且给出男女之间的暧昧关系。现在求一个学习小组，使得里面的任何两个人之间不能有暧昧关系。
求这个学习小组最多能够有多少人？
分析：
    二分图求最大独立集合
|最大独立集合| + |最小顶点

覆盖| == |V|。且在二分图当中有|最大匹配| == |最小顶点覆盖|

  一般题的正常做法：

我们把男同学放左边,女同学放右边,如果男i与女j存在关系,那么左i与右j之间就连一条无向边. 其实最终我们要求的就是该二分图的最大独立集.

但这题的男女关系未说明，这里就是来自：https://blog.****.net/u013480600/article/details/38638219

的解释

//二分图最大匹配模板,二分图都是无向图
//调用下面算法前，保证本图是二分图
/*************vecotr模板*****************/
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
const int maxn = 510;

struct Max_Match
{
	int n;//左右点集大小,点从1开始编号
	vector<int> g[maxn];//g[i]表示左边第i个点邻接的右边点的集合
	bool vis[maxn];//vis[i]表示右边第i个点是否在本次match中被访问过
	int left[maxn];//left[i]==j表右边第i个点与左边第j个点匹配,为-1表无点匹配

	void init(int n)
	{
		this->n = n;
		
		for (int i = 0; i <= n; i++) g[i].clear();
		memset(left, -1, sizeof(left));
	}

	//判断从左u点是否可以找到一条增广路
	bool match(int u)
	{
		for (int i = 0; i<g[u].size(); i++)
		{
			int v = g[u][i];
			if (!vis[v])
			{
				vis[v] = true;
				if (left[v] == -1 || match(left[v]))//找到增广路
				{
					left[v] = u;
					return true;
				}
			}
		}
		return false;
	}

	//返回当前二分图的最大匹配数
	int solve()
	{
		int ans = 0;//最大匹配数
		for (int i = 0; i <n; i++)//每个左边的节点找一次增广路
		{
			memset(vis, 0, sizeof(vis));
			if (match(i)) ans++;//找到一条增广路,形成一个新匹配
		}
		return ans;
	}
}MM;
/*************vecotr模板*****************/

int main()
{
	int n;
	while (scanf("%d", &n)!=-1)
	{
		MM.init(n);
		for (int i = 0; i < n; i++)
		{
			int u, num;
			scanf("%d: (%d)", &u, &num);
			while (num--)
			{
				int v;
				scanf("%d", &v);
				MM.g[u].push_back(v);
			}
		}
		printf("%d\n", n - MM.solve() / 2);
	}
	return 0;
}