题目:http://acm.hdu.edu.cn/showproblem.php?pid=1068
二分图的最大独立集数=节点数(n)— 最大匹配数(m)
另外需要注意的是:
本题求出的最大匹配数是实际的两倍需要m/2
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
const int N=;
int a[N][N];
int match[N];
int use[N];
int n;
int dfs(int u)
{
for(int i=;i<n;i++)
{
if(a[u][i] && !use[i])
{
use[i]=;
if(match[i]==- || dfs(match[i]))
{
match[i]=u;
return ;
}
}
}
return ;
}
int bipartite()
{
int res=;
memset(match,-,sizeof(match));
for(int i=;i<n;i++)
{
memset(use,,sizeof(use));
if(dfs(i))
res++;
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
int q,p,m;
memset(a,,sizeof(a));
for(int i=;i<n;i++)
{
scanf("%d: (%d) ",&q,&m);
for(int j=;j<m;j++)
{
scanf("%d",&p);
a[q][p]=;
}
}
int x=n-bipartite()/;
printf("%d\n",x);
}
return ;
}