Girls and Boys

求最大独立集团  就是里面任意两个点都不能成边 求最大  最大独立集团=顶点数-最大匹配

要注意的是  该图为双向的  所以最大匹配要除以二

#include<bits/stdc++.h>
using namespace std;

int mp[1005][1005];//图
int used[1006];//记录循环每次使用情况
int vis[1005];//记录的是匹配情况
int n;//n为左图  m为右图
bool dfs(int  x)
{
    for(int j=0;j<n;j++)
    {
        if(mp[x][j]&&!used[j])
        {
            used[j]=1;
            if(!vis[j]||dfs(vis[j]))
              {
                  vis[j]=x;
                  return true;
              }
        }
    }
    return false;
}

int main()
{
    int k,cas,x,y;
    while(scanf("%d",&n)==1)
    {
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        int a,b,c;
        for(int i=0;i<n;i++)
        {   int q;
            scanf("%d: (%d)",&a,&q);
            while(q--)
            {
                scanf("%d",&b);
                mp[a][b]=1;
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            memset(used,0,sizeof(used));//每次的使用  需要清除
            if(dfs(i))ans++;
        }
        printf("%d
",n-ans/2);
    }

}