Cod sursa(job #1022859)

Utilizator drobertDumitru Robert drobert Data 6 noiembrie 2013 00:52:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
using namespace std;
ifstream cin( "sortaret.in" );
ofstream cout( "sortaret.out" );

int n, x, y, m, v[ 50001 ];
int *a[ 50001 ], viz[ 50001 ];

void dfs( int k )
{
	int i;
	viz[ k ] = 1;
	for ( i = 1; i <= a[ k ][ 0 ]; i++ )
		if ( !viz[ a[ k ][ i ] ] ) dfs( a[ k ][ i ] );
	v[ ++v[ 0 ] ] = k;
}

int main()
{
	int i;
	cin >> n >> m;
	for ( i = 1; i <= n; i++ )
	{
		a[ i ] = ( int * ) realloc( a[ i ],sizeof( int ) );
		a[ i ][ 0 ] = 0;
	}
	for ( i = 1; i <= m; i++ )
	{
		cin >> x >> y;
		a[ x ][ 0 ]++;
		a[ x ] = ( int * ) realloc( a[ x ], ( a[ x ][ 0 ] + 1 ) * sizeof( int ) );
		a[ x ][ a[ x ][ 0 ] ] = y;
	}
	for ( i = 1; i <= n; i++ )
		if ( !viz[ i ] ) dfs( i );
	for ( i = n; i > 0; i-- )
		cout << v[ i ] << " ";
}