Cod sursa(job #1391769)

Utilizator PatrikStepan Patrik Patrik Data 18 martie 2015 10:14:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

#define NMAX 50001

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

void citire();
void solve();

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

void citire()
{
	int x , y;
	freopen("sortaret.in" , "r" , stdin );
	scanf("%d%d" , &N , &M );
	for(int i = 1 ; i <= M ; ++i )
	{
		scanf("%d%d" , &x , &y );
		G[x].push_back(y);
		grad[y]++;
	}
}

void solve()
{
	int nod;

	freopen("sortaret.out" , "w" , stdout );

	for(int i = 1 ; i <= N ; ++i )
		if(!grad[i])
			Q.push(i);
	while(!Q.empty()){
		nod = Q.front();
		Q.pop();
		printf("%d " , nod);
		for(int i = 0 ; i < G[nod].size();  ++i )
			if(--grad[G[nod][i]] == 0)
				Q.push(G[nod][i]);
	}
}