Girls and Boys

题目大意：

                 给你n个人编号为0 - n-1，他们有些人相互之间存在一种关系见题目描述，现在告诉你这些关系，但是有些给出的是x和y但没有说y和x，所以我们可以补全这里或者只要满足一个就行，如果补全就是无向图，然后求最多有多少个人他们之间没有两个人是存在这种关系的！

题目思路：

                这是最大独立集的裸题，而我们知道最大独立集= 定点数-最大匹配，而如果是无向图最大匹配就要除以2，所以我们只需跑一边最大匹配就行！

AC代码:

#include<cstring>
#include<cstdio>

const int maxn = 1e3+10;

bool vis[maxn],mp[maxn][maxn];
int link[maxn];

int n;

bool dfs(int u){
    for(int i=1;i<=n;i++){
        if(!vis[i]&&mp[u][i]){
            vis[i]=true;
            if(link[i]==-1||dfs(link[i])){
                link[i]=u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    while(~scanf("%d",&n)){
        memset(link,-1,sizeof(link));
        memset(mp,false,sizeof(mp));
        for(int i=1;i<=n;i++){
            int id,num=0,j=1;
            char str[20];
            scanf("%d: %s",&id,str);id++;
            int len = strlen(str);
            while(j<len-1){
                num=num*10+str[j]-'0';j++;
            }
            while(num--){
                int v;scanf("%d",&v);v++;
                mp[id][v]=mp[v][id]=true;
            }
        }
        int ans = 0;
        for(int i=1;i<=n;i++){
            memset(vis,false,sizeof(vis));
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans/2);
    }
    return 0;
}