Pagini recente » Cod sursa (job #163647) | Cod sursa (job #646209) | Cod sursa (job #998822) | Cod sursa (job #272510) | Cod sursa (job #2760501)
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
fin >> n >> m;
// edges[node] gives us all the outgoing edges from [node].
vector<vector<int>> edges(n);
for (int i = 0; i < m; i++) {
int from, to;
fin >> from >> to;
from--;
to--;
edges[from].push_back(to);
}
// edges now contains our entire graph.
vector<int> degree(n);
for (int i = 0; i < n; i++) {
for (const auto& to : edges[i]) {
// We have an edge from [i] to [to].
// Therefore the in degree of [to] should go up.
degree[to]++;
}
}
stack<int> nodes;
for (int i = 0; i < n; i++) {
if (degree[i] == 0) {
nodes.push(i);
}
}
vector<int> topologicalSort;
while (!nodes.empty()) {
const int cur = nodes.top();
nodes.pop();
for (const auto& to : edges[cur]) {
degree[to]--;
nodes.push(to);
}
topologicalSort.push_back(cur);
}
for (const auto& node : topologicalSort) {
fout << node + 1 << " ";
}
fout << "\n";
return 0;
}