Girls and Boys

题意

有 $n$ 个学生，每个学生可能和若干个其他异性学生有过恋爱关系
现在要选择一些学生形成集合，使得集合内任意两个学生之间都没有过恋爱关系

思路

把学生抽象成点，恋爱关系抽象成边，题意即是求：最大独立集，集合内部没有任何的边

最大独立集 $\iff$ 最小点覆盖的补集

但是这里没有明确二分图的左右点，我们可以将所有点复制，一个放置左边，一个放在右边，
那么这张新图的最大匹配数量其实就是原图的最大匹配的两倍，相当于把原图整张复制了，
这样子就不用考虑左右点的明确

// Problem: Girls and Boys
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=1068
// Memory Limit: 65 MB
// Time Limit: 20000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long longconst int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;typedef long long ll;std::vector<std::vector<int>> g;
std::vector<bool> used;
std::vector<int> match;bool dfs(int u){for(auto v : g[u])if(!used[v]){used[v] = true;if(!match[v] || dfs(match[v])){match[v] = u;return true;}}return false;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;while(~scanf("%d", &n)){g.assign(n + 1, std::vector<int>());match.assign(n + 1, 0);fore(i, 0, n){int u, k;scanf("%d: (%d)", &u, &k);while(k--){int v;scanf("%d", &v);g[u].push_back(v);}}int num = 0;fore(i, 0, n){used.assign(n, false);if(dfs(i))	++num;}std::cout << n - num / 2 << endl;}return 0; 
}