Cod sursa(job #1196926)

Utilizator stef93Stefan Gilca stef93 Data 9 iunie 2014 21:11:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <queue>
#include <list>

using namespace std;

list<int> graf[50001];
queue<int> coada;
int grad[50001];
int n, m;

void solve(ofstream &out) {
	int i, nod;
	for (i = 1; i <= n; i++) {

		if (grad[i] == 0) {
			coada.push(i);
		}
	}
	for (i = 1; i <= n; i++) {
		if (coada.empty() == true) {
			cerr << "Graful contine cicluri\n";
			exit(1);
		}
		nod = coada.front();
		coada.pop();
		out << nod << ' ';

		for (list<int>::iterator it = graf[nod].begin(); it != graf[nod].end();
				it++) {
			grad[*it]--;
			if (grad[*it] == 0) {
				coada.push(*it);
			}
		}
	}
}

int main() {
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	int i, x, y;
	in >> n >> m;
	for (i = 0; i < m; i++) {
		in >> x >> y;
		graf[x].push_front(y);
		grad[y]++;

	}
	solve(out);
	return 0;
}