Cod sursa(job #772340)

Utilizator danalex97Dan H Alexandru danalex97 Data 29 iulie 2012 11:45:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

#define Nmax 50011

ifstream F("sortaret.in");
ofstream G("sortaret.out");

int N,M; 

queue< int > Q,Rez; 
vector< int > Leg[Nmax]; 

int Grad[Nmax];

int main()
{
	F>>N>>M;
	for ( int i=1;i<=N;++i )
	{
		int x,y;
		F>>x>>y;
		Leg[x].push_back( y );
		++ Grad[y];
	}
	
	for ( int i=1;i<=N;++i )
		if ( !Grad[i] )
			Q.push( i );
	
	while ( Q.size() )
	{
		int Nod=Q.front();
		Q.pop();
		
		for ( vector<int>::iterator it=Leg[ Nod ].begin(); it!=Leg[ Nod ].end() ; ++it )
			if ( Grad[ *it ] )
			{
				--Grad[ *it ];
				if ( ! Grad[ *it ] )
					Q.push( *it );
			}
		
		Rez.push( Nod );
	}
	
	for ( ;Rez.size(); Rez.pop() ) G<< Rez.front() <<' ';
	G<<'\n';
}