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