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

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