# Poj Solution 2594

```http://poj.org/problem?id=2594

#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
#define null 0
const int size=510;
bool w[size][size];
int maxmatch(int n,int m,bool w[][size],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=1;link=-1;
from[0]=-1;
q[0]=size-1;
p_m[size-1]=i;
for(t=0;t<s;t++)
{
now=q[t];
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(p_m[j]==-1)
{
link=s-1;
break;
}
}
}
if(j<m)break;
}
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;

}
}
}
int an;
for(i=0,an=0;i<n;i++)
{
if(p)p[i]=p_n[i];

if(p_n[i]>=0)an++;

}
return an;

}
vector< int > e[500];
bool sign[500];
void find( int s, int r )
{
int i, t;
sign[s] = 1;
if( s != r ) w[r][s] = 1;

for( i=0; i<e[s].size(); i++ )
if( !sign[ t=e[s][i] ] )
find( t, r );

}
int main()
{
int n, m, i, j, a, b, ans, k;
while( scanf( "%d %d", &n, &m ) == 2 )
{
if( n == 0 && m == 0 ) break;
memset( w, 0, sizeof( w ) );
for( i=0; i<n; i++ )
e[i].clear();
for( i=0; i<m; i++ )
{
scanf( "%d %d", &a, &b );
w[a-1][b-1] = 1;
e[a-1].push_back( b-1 );
}
for( k=0; k<n; k++ )
{
memset( sign, 0, n );
find( k, k );
}
ans = n - maxmatch( n, n, w, 0 );
printf( "%dn", ans );

}

return 0;
}

```
This entry was posted in poj. Bookmark the permalink.