Poj Solution 1112

http://poj.org/problem?id=1112

#include <vector>
#include <algorithm>
#include <stdio.h>
#include <memory.h>
#include <math.h>

using namespace std;

vector<int> unknow[100];
vector< pair<int,int> > s;

int sign[100];
bool e[100][100];
int flag[110][110];

int a, b, an, bn;

bool search( int k, int key )
{
    int i;

    sign[k] = key;

    if( key == a ) an++;
    else bn++;

    for( i=0; i<unknow[k].size(); i++ )
        if( sign[ unknow[k][i] ] == 0 )
        {
            if( !search( unknow[k][i], a+b-key ) ) 
                return false;
        }
        else if( sign[ unknow[k][i] ] == key ) 
            return false;

    return true;
}


int main()
{
    int n, i, j, k, x, y;

    scanf( "%d", &n );

    for( i=0; i<n; i++ )
    for( j=0; j<n; j++ )
        e[i][j] = ( i == j );

    for( i=0; i<n; i++ )
    {
        unknow[i].clear();
        while( 1 )
        {
            scanf( "%d", &j );
            if( j == 0 ) break;
            j--;
            e[i][j] = true;
        }
    }

    for( i=0; i<n; i++ )
    for( j=0; j<n; j++ )
        if( !e[i][j] || !e[j][i] ) unknow[i].push_back( j );
    

    memset( sign, 0, sizeof(sign) );
    memset( flag, 0, sizeof(flag) );

    a = 1, b = 2;

    s.clear();
    for( i=0; i<n; i++ )
        if( sign[i] == 0 )
        {
            
            an = bn = 0;
            if( !search( i, a ) ) break;

            s.push_back( pair<int,int>( an, bn ) );
            a += 2, b += 2;
        }

    if( i < n )
    {
        printf( "No solutionn" );
        return 0;
    }

    flag[0][0] = true;

    for( k=0; k<s.size(); k++ )
    for( i=n-1; i>=0; i-- )
    for( j=n-1; j>=0; j-- )
        if( flag[i][j] != 0 )
        {
            if( ( x = s[k].first+i ) < n && ( y = s[k].second+j ) < n && !flag[x][y] )
                flag[x][y] = k+1;
            if( ( x = s[k].first+j ) < n && ( y = s[k].second+i ) < n && !flag[y][x] )
                flag[y][x] = -(k+1);
        }

    x = 0; y = n;
    for( i=1; i<n; i++ )
        if( flag[i][n-i] != 0 && abs( i*2-n ) < y )
            x = i, y = abs( i*2-n );

    y = n-x;

    vector< int > s1,s2;

    while( x || y )
    {
        k = abs( flag[x][y] ) - 1;
        a = k*2+1; b = k*2+2;

        if( flag[x][y] < 0 ) swap( a, b );

        for( i=0; i<n; i++ )
            if( sign[i] == a )
                s1.push_back( i+1 );
            else if( sign[i] == b )
                s2.push_back( i+1 );

        a = s[k].first, b = s[k].second;
        if( flag[x][y] < 0 ) swap( a, b );

        x -= a, y-=b;
    }

    printf( "%d", s1.size() );
    for( i=0; i<s1.size(); i++ )
        printf( " %d", s1[i] );
    printf( "n" );

    printf( "%d", s2.size() );
    for( i=0; i<s2.size(); i++ )
        printf( " %d", s2[i] );
    printf( "n" );

    return 0;
}