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