http://poj.org/problem?id=1087
#include<iostream>
#include"string.h"
using namespace std;
#define null 0
const int size=1000;
bool w[size][size];
void maxmatch(int n,int m,int *p)
{
int p_n[size];
int p_m[size];
bool sign[size];
int q[size],from[size],s,t;
int i,j,link,now,h;
for(i=0;i<n;i++)p_n[i]=-1;
for(j=0;j<m;j++)p_m[j]=-1;
for(i=0;i<n;i++)
if(p_n[i]==-1)
{
for(j=0;j<m;j++)sign[j]=0;
s=0;
for(j=0;j<m;j++)
if(w[i][j]!=null)
{
q[s]=j;
from[s++]=-1;
sign[j]=1;
}
for(t=0;t<s;t++)
{
now=q[t];
if(p_m[now]==-1)
{
link=t;
break;
}
else
{
for(j=0;j<m;j++)
if(w[p_m[now]][j]!=null&&sign[j]==0)
{
sign[j]=1;
q[s]=j;
from[s++]=t;
}
}
}
if(t<s)
{
while(from[link]!=-1)
{
h=from[link];
p_m[q[link]]=p_m[q[h]];
p_n[p_m[q[h]]]=q[link];
link=h;
}
p_m[q[link]]=i;
p_n[i]=q[link];
}
}
for(i=0;i<n;i++)p[i]=p_n[i];
return ;
}
int main()
{
bool map[501][501];
char name[501][30],w1[30],w2[30];
char device[501][30];
int n,m,e,i,j,a,b,k,an[510],tn;
cin>>n;
tn=n;
for(i=0;i<n;i++)
cin>>name[i];
cin>>m;
for(i=0;i<m;i++)
{
cin>>w1>>device[i];
for(a=0;a<n;a++)
if(strcmp(device[i],name[a])==0)break;
if(a==n)strcpy(name[n++],device[i]);
}
cin>>e;
for(i=0;i<501;i++)
for(j=0;j<501;j++)
if(i!=j)map[i][j]=0;
else map[i][j]=1;
for(i=0;i<e;i++)
{
cin>>w1;
cin>>w2;
for(a=0;a<n;a++)
if(strcmp(w1,name[a])==0)break;
if(a==n)strcpy(name[n++],w1);
for(b=0;b<n;b++)
if(strcmp(w2,name[b])==0)break;
if(b==n)strcpy(name[n++],w2);
//if(a<n&&b<n)
map[a][b]=1;
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
map[i][j]|=map[i][k]&&map[k][j];
for(i=0;i<m;i++)
for(j=0;j<n;j++)
w[i][j]=0;
for(i=0;i<m;i++)
{
for(a=0;a<n;a++)
if(strcmp(device[i],name[a])==0)break;
for(j=0;j<tn;j++)w[i][j]=map[a][j];
}
maxmatch(m,tn,an);
int answer;
for(i=0,answer=0;i<m;i++)
if(an[i]<0)answer++;
cout<<answer<<endl;
return 0;
}