Pagini recente » Cod sursa (job #613990) | Cod sursa (job #2293939) | Cod sursa (job #1902785) | Cod sursa (job #1752768) | Cod sursa (job #2064313)
#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;
}