POJ 1466 Girls and Boys （挑战程序设计竞赛，二分图最大独立集）

挑战程序设计竞赛，283页，二分图最大独立集
二分图的最大独立集
题目意思:
在一群男女生之间存在浪漫关系，且只存在于男女之间，现给出存在关系的人的编号，但没给具体的男女性别，
现在要求一个集合，在集合中任意两人都不存浪漫关系，输出集合中元素的个数.

本题要点：
1、定理：
二分图的最大独立集 = 总点数 - 最大匹配数
2、这里采用邻接表来存图。用增广路算法求出最大匹配数。
二分图匹配，因为没有分左右每对匹配会出现两次。 最后算出来的 ans 要除以2;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 510, MaxM = 250010;;
int head[MaxN], ver[MaxM], Next[MaxM], match[MaxN];
int n, tot;
bool vis[MaxN];void add(int x, int y)
{
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}bool dfs(int x)
{
    for(int i = head[x]; i; i = Next[i]){
    int y = ver[i];if(!vis[y]){
    vis[y] = true;if(!match[y] || dfs(match[y])){
    match[y] = x;return true;}}}return false;
}int main()
{
    char s[10] = {
    0};int k;while(scanf("%d", &n) != EOF){
    int j;tot = 0;memset(head, 0, sizeof head);memset(Next, 0, sizeof Next);memset(match, 0, sizeof match);for(int i = 0; i < n; ++i){
    scanf("%s", s);	scanf("%s", s);	s[strlen(s) - 1] = '\0';k = atoi(s + 1);while(k--){
    scanf("%d", &j);		add(i, j);}}int ans = 0;for(int i = 0; i < n; ++i){
    memset(vis, 0, sizeof vis);if(dfs(i))++ans;}printf("%d\n", n - ans / 2);}return 0;
}/* 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 */