Cod sursa(job #784242)

Utilizator f.v.antonFlavius Anton f.v.anton Data 5 septembrie 2012 12:23:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <vector>

#define NMAX 50005

using namespace std;

list<int> toposort(vector<int> graph[], vector<int> deg, int n)
{
	int i, node;
	list<int> l;
	queue<int> q;
	vector<int>::iterator elem;

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

	while (!q.empty()) {
		node = q.front();
		q.pop();
		l.push_back(node);

		for(elem = graph[node].begin(); elem != graph[node].end();
				elem++) {
			deg[*elem]--;
			if (deg[*elem] == 0)
				q.push(*elem);
		}
	}
	return l;
}

void print(fstream& g, list<int> l)
{
	while(!l.empty()) {
		g << l.front() << " ";
		l.pop_front();
	}
}

int main(void)
{
	fstream f("sortaret.in", ios::in), g("sortaret.out", ios::out);
	int n, m, i, val1, val2;
	vector<int> deg, graph[NMAX];
	list<int> l;

	f >> n >> m;
	deg.resize(n+1);

	for (i = 1; i <= m; i++) {
		f >> val1 >> val2;
		graph[val1].push_back(val2);
		deg[val2]++;
	}
	
	l = toposort(graph, deg, n);
	print(g, l);

	f.close();
	g.close();
	return 0;
}