[POJ] 1094 - Sorting It All Out - http://kuoe0.ch/410/poj-1094-sorting-it-all-out/

1094 – Sorting It All Out.cpp

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