Cod sursa(job #1181972)

Utilizator bluetigerTokes Atti bluetiger Data 4 mai 2014 13:20:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
// http://www.infoarena.ro/problema/sortaret
#include <fstream>
#include <vector>
using namespace std;

#define FOR(i, n) for (decltype(n) i = 0; i < n; ++i)
#define FORE(x, v) for (auto x : v)

int main() {
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");

	int N, M;
	in >> N >> M;

	vector<int> deg(N, 0);
	vector<vector<int>> edges(N);

	FOR(i, M) {
		int x, y;
		in >> x >> y; --x; --y;
		deg[y]++;
		edges[x].push_back(y);
	}

	vector<int> q;

	FOR (i, N) if (deg[i] == 0) q.push_back(i);

	FOR (i, N) {
		FORE (x, edges[q[i]]) {
			if (--deg[x] == 0) q.push_back(x);
		}
	}

	FORE(x, q) out << ++x << " ";

	return 0;
}