Cod sursa(job #152912)

Utilizator amadaeusLucian Boca amadaeus Data 9 martie 2008 21:55:52
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <stdlib.h>

#define NX 100010

int V, E, list[ NX ], col[ NX ], deg[ NX ], *G[ NX ];

void cit() {
	int u, v, i;
	
	scanf( "%d%d", &V, &E );
	for( ; E; E-- ) {
		scanf( "%d %d ", &u, &v );
		deg[ u ]++;
     }
	for( i = 1; i <= V; i++ ) {
		G[i] = (int *) malloc( (deg[i] + 1) * sizeof( int ) );
		deg[i] = 0;
     }
	rewind( stdin );
	scanf( "%d%d", &V, &E );
	for( ; E; E-- ) {
		scanf( "%d %d ", &u, &v );
		G[u][ deg[u]++ ] = v;
	}
	for( i = 1; i <= V; i++ )
		G[ i ][ deg[i] ] = -1;
}

void DFS( int u ) {
	int *v;

	col[ u ] = 1;
	for( v = G[u]; *v != -1; v++ )
		if( col[ *v ] == 0 )
			DFS( *v );
     list[ ++list[0] ] = u;
}

void rez() {
	int i;
	
	for( i = 1; i <= V; i++ )
		if( col[ i ] == 0 )
			DFS( i );
}

void scr() {
	int i;

	for( i = list[0]; i; i-- )
		printf( "%d ", list[i] );
}

int main() {
	freopen( "sortaret.in", "r", stdin );
	freopen( "sortaret.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}