Cod sursa(job #482507)

Utilizator barneystinsonBarney barneystinson Data 3 septembrie 2010 18:53:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <vector>
#define NOD_MAX 500001
using namespace std;

vector <int> graf[NOD_MAX];
int N, M, viz[NOD_MAX], sol[NOD_MAX], p;

void reading(){
	
	scanf( "%d %d", &N, &M );
	int nod1, nod2;
	for( int i=1 ; i<=M ; ++i ){
		scanf( "%d %d", &nod1, &nod2 );
		graf[nod1].push_back(nod2);
	}
	
}

void sort_top_dfs( int s ){
	
	for( unsigned int i=0 ; i< graf[s].size() ; ++i ){
		sort_top_dfs( graf[s][i] );
	}
	sol[++p]=s;
	viz[s] = 1;
	
}

void writing(){
	
	for( int i=N ; i>=1 ; --i ){
		printf( "%d " , sol[i] );
	}
	
}

int main(){
	freopen( "sortaret.in" , "r" , stdin );
	freopen( "sortaret.out" , "w" , stdout );
	
	reading();
	
	for( int i=1 ; i<=N ; i++ ){
		if( !viz[i] ){
			sort_top_dfs(1);
		}
	}
	
	writing();
	
	return 0;
}