Cod sursa(job #1239422)

Utilizator PatrikStepan Patrik Patrik Data 9 octombrie 2014 00:11:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define MAX 50001
#define pb push_back

vector<int> G[MAX] ;
queue<int> Q;
int N , M , grad[MAX];

int main()
{
	int x , y , nod , i , j ;

	freopen("sortaret.in" , "r" , stdin );
	freopen("sortaret.out" , "w" , stdout );

	scanf("%d%d" , &N , &M );
	for( i = 1 ; i <= M ; ++i )
	{
		scanf("%d%d" , &x , &y );
		G[x].pb(y);
		grad[y]++;
	}

	for(int i = 1 ; i <= N ; ++i )
		if(!grad[i])Q.push(i);

	for(;!Q.empty();Q.pop())
	{
		nod = Q.front();
		printf("%d " , nod);
		for(vector<int>::iterator it = G[nod].begin() ; it != G[nod].end() ; ++it )
		{
			grad[*it]--;
			if(!grad[*it])Q.push(*it);
		}
	}



	return 0;
}