Cod sursa(job #699556)

Utilizator joli94Apostol Adrian Alexandru joli94 Data 29 februarie 2012 20:07:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

const int N = 50001 ;

vector <int> v[N];
queue <int> q;
int d[N];

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