Cod sursa(job #2064313)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 12 noiembrie 2017 10:23:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <queue>


class DGraph {
public:
	DGraph(int _n) : n(_n), nodes(_n, std::unordered_set<int>()), deps(_n, 0) { }

	void add(int u, int v) {
		u = u - 1;
		v = v - 1;

		if (nodes[u].find(v) != nodes[u].end())
			return;

		nodes[u].insert(v);
		deps[v] = deps[v] + 1;
	}

	void print_top_sort(std::ostream& out) {
		std::vector<int> order(n, -1);
		int pos = 0;

		std::queue<int> q;
		for (int i = 0; i < n; i++) {
			if (deps[i] == 0) {
				order[pos++] = i;
				q.push(i);
			}
		}

		while (!q.empty()) {
			int k = q.front();
			q.pop();

			for (int i : nodes[k]) {
				deps[i] = deps[i] - 1;
				if (deps[i] == 0) {
					order[pos++] = i;
					q.push(i);
				}
			}
		}

		for (int i : order) {
			out << i + 1 << " ";
		}
		out << std::endl;
	}


private:
	int n;
	std::vector<std::unordered_set<int>> nodes;
	std::vector<int> deps;
};

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

	int n, m;
	in >> n >> m;

	DGraph g(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		in >> u >> v;
		g.add(u, v);
	}

	g.print_top_sort(out);

	return 0;
}