Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
[POJ] 1094 - Sorting It All Out - http://kuoe0.ch/410/poj-1094-sorting-it-all-out/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 50
vector< vector< int > > vertex, rev;
int in[ MAXN ], out[ MAXN ], visit[ MAXN ];
int n, e;
vector< int > topo;
bool DFS( int now ) {
visit[ now ] = 1;
for ( int i = 0; i < vertex[ now ].size(); ++i ) {
int next = vertex[ now ][ i ];
if ( !visit[ next ] )
if ( !DFS( next ) )
return 0;
if ( visit[ next ] == 1 )
return 0;
}
visit[ now ] = -1;
return 1;
}
bool FindTopo() {
int tempout[ MAXN ];
memcpy( tempout, out, sizeof( out ) );
for ( int k = 0; k < n; ++k ) {
int now = -1;
for ( int i = 0; i < n; ++i )
if ( !tempout[ i ] ) {
if ( now == -1 )
now = i;
else
return 0;
}
tempout[ now ] = -1;
topo.push_back( now );
for ( int i = 0; i < rev[ now ].size(); ++i )
--tempout[ rev[ now ][ i ] ];
}
return 1;
}
int main() {
while ( ~scanf( "%d %d", &n, &e ) && n && e ) {
rev = vertex = vector< vector< int > >( n );
memset( in, 0, sizeof( in ) );
memset( out, 0, sizeof( out ) );
bool state = 0;
int inNode = n, outNode = n;
for ( int i = 0; i < e; ++i ) {
char a, b;
scanf( " %c < %c", &a, &b );
vertex[ a - 'A' ].push_back( b - 'A' );
rev[ b - 'A' ].push_back( a - 'A' );
if ( !in[ b - 'A' ] )
--inNode;
if ( !out[ a - 'A' ] )
--outNode;
++in[ b - 'A' ];
++out[ a -'A' ];
if ( !state ) {
for ( int j = 0; j < n; ++j ) {
memset( visit, 0, sizeof( visit ) );
topo = vector< int >();
if ( !DFS( j ) ) {
state = 1;
printf( "Inconsistency found after %d relations.\n", i + 1 );
break;
}
if ( FindTopo() ) {
state = 1;
printf( "Sorted sequence determined after %d relations: ", i + 1 );
for ( int k = topo.size() - 1; k >= 0; --k )
putchar( topo[ k ] + 'A' );
puts( "." );
break;
}
}
}
}
if ( !state )
puts( "Sorted sequence cannot be determined." );
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.