传送门：点击打开链接
题意：男生可能和女生有喜欢的关系，现在要分组，使得组里面没有任何两个人有喜欢的关系
思路：裸最大独立集的题目，关于二分图，可以去看下另外一篇二分图总结的文章
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
const int MX = 5e2 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int match[MX];
bool G[MX][MX], vis[MX];
bool DFS(int vn, int u) {
for(int v = 1; v <= vn; v++) {
if(G[u][v] && !vis[v]) {
vis[v] = 1;
if(match[v] == -1 || DFS(vn, match[v])) {
match[v] = u;
return 1;
}
}
}
return 0;
}
int BM(int n) {
int res = 0;
memset(match, -1, sizeof(match));
for(int u = 1; u <= n; u++) {
memset(vis, 0, sizeof(vis));
if(DFS(n, u)) res++;
}
return res;
}
int main() {
int n, m; //FIN;
while(~scanf("%d", &n)) {
memset(G, 0, sizeof(G));
for(int i = 1; i <= n; i++) {
char temp[1000];
scanf("%*s%s", temp);
sscanf(temp, "(%d)", &m);
for(int j = 1; j <= m; j++) {
int t; scanf("%d", &t);
G[i][t + 1] = 1;
G[t + 1][i] = 1;
}
}
printf("%d\n", n - BM(n) / 2);
}
return 0;
}