Pagini recente » Cod sursa (job #2820997) | Cod sursa (job #2864573) | Cod sursa (job #567915) | Cod sursa (job #2170534) | Cod sursa (job #1243927)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int main (int argc, char const *argv[]) {
int n, m;
in>>n>>m;
vector<set<int>> graph;
graph.resize(n + 1);
vector<int> incoming;
incoming.resize(n + 1);
vector<int> sorted;
for (int i = 0; i < m; ++i) {
int x, y;
in>>x>>y;
graph[x].insert(y);
}
for (const auto& neighbours : graph) {
for (const auto& neighbour : neighbours) {
incoming[neighbour]++;
}
}
queue<int> sort_queue;
for (int i = 1; i <= n; ++i) {
if(incoming[i] == 0) {
sort_queue.push(i);
}
}
while (!sort_queue.empty()) {
int current = sort_queue.front();
sort_queue.pop();
sorted.push_back(current);
for (const auto& neighbour : graph[current]) {
if ((--incoming[neighbour]) == 0) {
sort_queue.push(neighbour);
}
}
}
for (const auto& x : sorted) {
out<<x<<" ";
}
return 0;
}