Cod sursa(job #699510)

Utilizator alutzuAlexandru Stoica alutzu Data 29 februarie 2012 19:46:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std ;

struct NOD { int nr , cost ; } ;

const int NMAX = 50001 ;

vector<int> mat[NMAX];
queue<int> q;

int d[NMAX];

int main ( )
{
	freopen ( "sortaret.in", "r", stdin ) ;
	freopen ( "sortaret.out", "w", stdout ) ;
	
	int N , M , i , x , y ;
	
	scanf ( "%d%d", & N , & M ) ;
	
	for ( i = 1 ; i <= M ; ++ i )
	{
		scanf ( "%d%d", & x, &y ) ;
		
		mat[x].push_back ( y ) ;
		++d[y];
	}
	
	for ( i = 1 ; i <= N ; ++ i )
		if ( ! d[i] )
		{
			q.push ( i ) ;
		}
	
		
	while ( ! q.empty () )
	{
		x = q.front ( ) ;
		printf ( "%d " , x ) ;
		q.pop ( ) ;
		
		for ( size_t i = 0 ; i < mat[x].size () ; ++ i )
		{
			y = mat[x][i] ;
			--d[y];
			if ( d[y] == 0 )
				q.push ( y ) ;
		}
	}
	
	return 0 ;
}