Cod sursa(job #1241444)

Utilizator adysnookAdrian Munteanu adysnook Data 13 octombrie 2014 15:58:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <list>
#include <vector>
#include <unordered_set>

using namespace std;

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

int main(){
	int n, m, i, x, y;
	in >> n >> m;
	list<int> *n_out = new list<int>[n + 1];
	int *n_gint = new int[n + 1];
	for (i = 1; i <= n; ++i){
		n_gint[i] = 0;
	}
	for (i = 0; i < m; ++i){
		in >> x >> y;
		n_out[x].push_back(y);
		++n_gint[y];
	}
	unordered_set<int> s;
	for (i = 1; i <= n; ++i){
		if (!n_gint[i])
			s.insert(i);
	}
	list<int> l;
	while (!s.empty()){
		x = *s.begin();
		s.erase(x);
		l.push_back(x);
		for (auto v : n_out[x]){
			--n_gint[v]; --m;
			if (!n_gint[v])
				s.insert(v);
		}
	}
	if (m)
		return -1;
	for (auto v : l){
		out << v << " ";
	}
	return 0;
}