Cod sursa(job #657718)

Utilizator razvan2006razvan brezulianu razvan2006 Data 7 ianuarie 2012 11:26:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
 # include <fstream>
 # include <vector>
 # include <queue>
 
 # define pb push_back
 # define dim 50001
 
 using namespace std;

 ifstream f("sortaret.in");
 ofstream g("sortaret.out");

 int n, m;

 vector <int> a[ dim ];
 queue <int> q;
 
 int grad[ dim ];
 
 void citire()
 {
	 int i, x, y;
	 
	 f >> n >> m;
	 for ( i = 1 ; i <= m ; i++ )
	 {
		 f >> x >> y;
		 a[ x ].pb( y );
		 grad[ y ]++;
	 }
	 
	 for ( i = 1; i <= n; i++ ) 
		if ( grad[ i ] == 0 ) 
			q.push( i );
		
 }
 
 void rezolva()
 {
	 int xx, i;
	
	 while( !q.empty() )
	 {	
		xx = q.front();
		g << xx << " " ;
		for ( i = 0 ; i < a[ xx ].size() ; i++ )
		{	
			grad[ a[ xx ][ i ] ]--;
			if ( grad[ a[ xx ][ i ] ] == 0 )
				q.push( a[ xx ][ i ] );
		}
		q.pop();
	}
 }

int main()
{
	citire();
	rezolva();
	return 0;
}