Cod sursa(job #1436515)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 16 mai 2015 00:19:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <queue>
#include <list>
#define MAX 50010
using namespace std;

int deg[MAX];

int main(){
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	int n, m, i, node, a, b;
	queue<int> novert;
	list<int> *graph;
	list<int> slist;
	scanf("%d%d", &n, &m);
	graph = new list<int>[n+1];

	for(i = 0; i < m; i++){
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		deg[b]++;
	}

	for(i = 1; i <= n; i++)
		if(!deg[i])
			novert.push(i);

	while(!novert.empty()){
		n = novert.front();
		novert.pop();
		slist.push_back(n);
		while(!graph[n].empty()){
			node = graph[n].front();
			graph[n].pop_front();
			deg[node]--;
			if(!deg[node])
				novert.push(node);
		}
	}
	while(!slist.empty()){
		n = slist.front();
		slist.pop_front();
		printf("%d ", n);
	}
	printf("\n");
	delete [] graph;
	return 0;
}