Girls and Boys

/*初次思考：给出你一个点阵，然后让你求最大连通图的点数并查集想法，找点#错误：题意没理解明白题意：找出一个最大集合使得任意两个人没有关系因为有关系的肯定是男女（暂时不考虑性取向的问题）所以就将整个关系图，联系到了二分图上，进而用到二分匹配问题的解决方案用到“匈牙利算法”要求最大的没有关系的集合，就是总顶点数-最大匹配数*/#include<bits/stdc++.h>using namespace std;int n,u,m,v;/***********************二分匹配模板**************************/const int MAXN=1010;int g[MAXN][MAXN];//编号是0~n-1的 int linker[MAXN];//记录匹配点i的匹配点是谁bool used[MAXN];bool dfs(int u)//回溯看能不能通过分手来进行匹配{    int v;    for(v=0;v<n;v++)        if(g[u][v]&&!used[v])        //如果有这条边，并且这条边没有用过        {            used[v]=true;            if(linker[v]==-1||dfs(linker[v]))//如果这个点没有匹配过，并且能找到匹配点，那么就可以以这个边作为匹配点            {                linker[v]=u;                return true;            }            }      return false;  }    int hungary()//返回最大匹配数{    int res=0;    int u;    memset(linker,-1,sizeof(linker));    for(u=0;u<n;u++)    {        memset(used,0,sizeof(used));        if(dfs(u))//如果这个点有匹配点             res++;    }     return res;   }/***********************二分匹配模板**************************/void init(){    memset(g,0,sizeof g);}int main(){    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    while(scanf("%d",&n)!=EOF){        init();        for(int i=0;i<n;i++){            scanf("%d: (%d)",&u,&m);            for(int j=0;j<m;j++){                scanf("%d",&v);                g[u][v]=1;            }        }//建图        int cur=hungary();        //cout<<cur<<endl;        printf("%d\n",n-cur/2);    }    return 0;}