最大独立集: 在N个点的图G中选出m个点,使这m个点两两之间没有边,求m最大值。如果图G满足二分图条件,则可以用二分图匹配来做。最大独立集点数 = N - 最大匹配数。
将孩子看成二分图里的 A,B集
若孩子a喜欢的动物号是孩子b喜欢的动物号
则连边,因为A,B集是同类,无向图
map[a][b]=1;map[b][a]=1;
实际上就是
最大独立集=顶点数-最大匹配数/2
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<stdio.h>
#include<string.h>
bool map[509][509];
int mark[509];
bool flag[509];
int m;
char A[509][9];
char B[509][9];
bool dfs(int x)
{
int i;
for(i=1;i<=m;i++)
{
if(map[x][i]==0||flag[i]) continue;
flag[i]=1;
if(mark[i]==0||dfs(mark[i]))
{
mark[i]=x;
return 1;
}
}
return 0;
}
int main()
{
int i,g,k,j;
int count;
while(scanf("%*d%*d%d",&k)!=EOF)
{
g=m=k;
memset(map,0,sizeof(map));
memset(mark,0,sizeof(mark));
count=0;
for(i=1;i<=k;i++)
{
scanf("%s",A[i]);
scanf("%s",B[i]);
}
for(i=1;i<=k;i++)
{
for(j=1;j<=k;j++)
{
if(strcmp(A[i],B[j])==0)
{
map[i][j]=1;
// map[j][i]=1;
}
}
}
for(i=1;i<=g;i++)
{
memset(flag,0,sizeof(flag));
if(dfs(i)==1) count++;
}
printf("%d\n",k-count/2);
}
}