Cod sursa(job #2338991)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 8 februarie 2019 10:34:16
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int MAXN = 5e4;
const int MAXM = 1e5;

int n, m;
vector<int> g[MAXN + 1];
int grad[MAXN + 1];
queue<int> nodes;

int main() {
	in >> n >> m;

	int x, y;
	for (int i = 1; i <= m; ++ i) {
		in >> x >> y;
		g[x].push_back(y);
		++ grad[y];
	}

	for (int i = 1; i <= n; ++ i) {
		if (grad[i] == 0) {
			nodes.push(i);
			break;
		}
	}

	while (nodes.size()) {
		for (auto x : g[nodes.front()]) {
			-- grad[x];
			if (grad[x] == 0) nodes.push(x);
		}
		out << nodes.front() << ' ';
		nodes.pop();
	}

	return 0;
}