HDU/HDOJ 3829 Cat VS Dog

この問題は、2つの集合しかないので、二分図の最大マッチングを思い浮かべやすいです.
だから私たちは猫が好きな人と犬が好きな人を2つの集合に分けました.
そしてA君がB君の嫌いなものが好きだったり、A君がB君の好きなものが嫌いだったりしたら
では、A君とB君の間を一つにします.
そして最大の独立集を求めて、答えです.
 
マイコード:

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

struct node
{
	char like[5];
	char dislike[5];
};
node cater[505],doger[505];
int n,m,p;
int num1,num2;
int used[505];
bool map[505][505];
int link[505];

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

int main()
{
	int i,j,ans;
	char s1[5],s2[5];
	while(scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		num1=0,num2=0,ans=0;
		memset(map,0,sizeof(map));
		memset(link,-1,sizeof(link));
		for(i=1;i<=p;i++)
		{
			scanf("%s%s",s1,s2);
			if(s1[0]=='C')
			{
				num1++;
				strcpy(cater[num1].like,s1);
				strcpy(cater[num1].dislike,s2);
			}
			if(s1[0]=='D')
			{
				num2++;
				strcpy(doger[num2].like,s1);
				strcpy(doger[num2].dislike,s2);
			}
		}
		for(i=1;i<=num1;i++)
			for(j=1;j<=num2;j++)
			{
				if(strcmp(cater[i].like,doger[j].dislike)==0||strcmp(cater[i].dislike,doger[j].like)==0)
					map[i][j]=true;
			}
		for(i=1;i<=num1;i++)
		{
			memset(used,0,sizeof(used));
			if(dfs(i))
				ans++;
		}
		printf("%d
",p-ans);
	}
	return 0;
}