# Poj Solution 1719

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

#include <stdio.h>
#include <memory.h>

int e[1000][1000], en[1000], col[1000];
int match[1000];

bool sign1[1000], sign2[1000];
int flag[1000];

bool search( int a )
{
int i, j;

sign1[a] = true;

for( i=0; i<en[a]; i++ )
{
j = e[a][i];
if( !sign2[j] )
{
sign2[j] = true;
if( match[j] == -1 || ( !sign1[match[j]] && search( match[j] ) ) )
{
match[j] = a;
flag[a] = j;
return true;
}
}
}

return false;
}

int main( )
{
int cas, i, c, r, a, b;

scanf( "%d", &cas );

while( cas-- )
{
scanf( "%d%d", &r, &c );

for( i=0; i<r; i++ )
en[i] = 0;

for( i=0; i<c; i++ )
{
scanf( "%d %d", &a, &b );
col[i] = a;
a--, b--;
e[a][en[a]++] = i;
e[b][en[b]++] = i;
}

memset( flag, -1, sizeof flag );
memset( match, -1, sizeof match );

for( i=0; i<r; i++ )
if( flag[i] == -1 )
{
memset( sign1, 0, sizeof sign1 );
memset( sign2, 0, sizeof sign2 );
if( !search( i ) )
break;
}

if( i < r )
printf( "NOn" );
else
{
for( i=0; i<c; i++ )
{
if( match[i] != -1 )
printf( "%d", match[i]+1 );
else
printf( "%d", col[i] );

if( i < c-1 )printf( " " );
else printf( "n" );
}
}
}

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.