题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1068
题目大意：有n个人，一些人认识另外一些人，选取一个集合，使得集合里的每个人都互相不认识，求该集合中人的最大个数。
解题思路：这题就是求最大独立集，但是这并不是两个集合，而是一个集合，所以求出最大匹配后需要/2，然后代公式：最大独立集=N-最大匹配。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+;
vector<int>v[N]; int n;
int link[N];
bool vis[N]; bool dfs(int u){
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!vis[t]){
vis[t]=true;
if(link[t]==-||dfs(link[t])){ //如果t尚未被匹配，或者link[t]即x可以找到其他能够替代的点,则把t点让给u匹配
link[t]=u;
return true;
}
}
}
return false;
} int max_match(){
memset(link,-,sizeof(link));
int ans=;
for(int i=;i<n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
return ans;
} int main(){
while(~scanf("%d",&n)){
for(int i=;i<=n;i++) v[i].clear();
memset(link,-,sizeof(link));
for(int i=;i<=n-;i++){
int num,t;
scanf("%d: (%d)",&num,&t);
for(int j=;j<=t;j++){
int x;
scanf("%d",&x);
v[num].push_back(x);
}
}
printf("%d\n",n-max_match());
}
return ;
}