题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1068
思路：
求一集合满足，两两之间没有恋爱关系
思路：
最大独立点集=顶点数-最大匹配数
这里给出的关系，看似有向边，实则是无向边，那么按照二分匹配处理的话，相当于一个人看作两个人来用，最后还是顶点数目-最大二分匹配数
因为之间一个人当作两个人用，二分匹配数目减半，即 = n - match()/2
或者也可以写成 = ( 2n - match() )/2 更容易理解
题目中n的大小没有说明，最好开大一点，最后测得的大小在500以内
代码：
#include <stdio.h>
#include <string.h>
const int maxn=;
int n;
int g[maxn][maxn],vis[maxn],who[maxn];
bool F(int x) {
for(int i=; i<n; ++i) {
if(g[x][i]&&!vis[i]) {
vis[i]=;
if(who[i]==-||F(who[i])) {
who[i]=x;
return true;
}
}
}
return false;
}
int main() {
while(~scanf("%d",&n)) {
memset(g,,sizeof(g));
memset(who,-,sizeof(who));
int temp=n,u,v,num;
while(temp--) {
scanf("%d: (%d)",&u,&num);
while(num--) {
scanf("%d",&v);
g[u][v]=g[v][u]=;
}
}
int sum=;
for(int i=; i<n; ++i) {
memset(vis,,sizeof(vis));
if(F(i)) sum++;
}
printf("%d\n",n-sum/);
}
return ;
}