Pagini recente » Cod sursa (job #1085024) | Cod sursa (job #372971) | Cod sursa (job #2494750) | Cod sursa (job #1131773) | Cod sursa (job #2914352)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
vector<int> dag[50001];
bitset<50001> is_visited;
stack<int> topological_order;
void dfs_traversal(int node) {
is_visited[node] = true;
int current_nr_neighbors = dag[node].size();
for (int i = 0; i < current_nr_neighbors; ++i) {
if (!is_visited[dag[node][i]]) {
dfs_traversal(dag[node][i]);
}
}
topological_order.push(node);
}
void print_topological_order() {
ofstream fout("sortaret.out");
while (!topological_order.empty()) {
fout << topological_order.top() << ' ';
topological_order.pop();
}
}
int main() {
ifstream fin("sortaret.in");
int nr_nodes, nr_arcs;
fin >> nr_nodes >> nr_arcs;
for (int i = 0; i < nr_nodes; ++i) {
int source_node, destination_node;
fin >> source_node >> destination_node;
dag[source_node].push_back(destination_node);
}
for (int i = 1; i <= nr_nodes; ++i) {
if (!is_visited[i]) {
dfs_traversal(i);
}
}
print_topological_order();
return 0;
}