Poj Solution 1087

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;
}