Pagini recente » Cod sursa (job #1821521) | Cod sursa (job #2413405) | Cod sursa (job #600145) | Cod sursa (job #3219887) | Cod sursa (job #2801269)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
struct Node {
vector<int> children;
int visited = false;
void add_child(int child_to_add) {
children.push_back(child_to_add);
}
} nodes[50001];
void topological_sort(int current_node, vector<int> &topological_sorted_nodes) {
nodes[current_node].visited = true;
for (auto child : nodes[current_node].children) {
if (nodes[child].visited == false) {
topological_sort(child, topological_sorted_nodes);
}
}
topological_sorted_nodes.push_back(current_node);
}
int main() {
int n, m;
f >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
f >> x >> y;
nodes[x].add_child(y);
}
vector<int> topological_sorted_nodes;
// how do I know which one is the father???
for (int i = 1; i <= n; ++i) {
if (nodes[i].visited == false) {
topological_sort(i, topological_sorted_nodes);
}
}
for (int i = n - 1; i >= 0; --i) {
g << topological_sorted_nodes[i] << " ";
}
return 0;
}