Pagini recente » Cod sursa (job #2439579) | Cod sursa (job #2241758) | Cod sursa (job #2517896) | Cod sursa (job #2126036) | Cod sursa (job #2916281)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#define MAX_NR_NODES 50000
using namespace std;
vector<int> graph[MAX_NR_NODES + 1];
bitset<MAX_NR_NODES + 1> is_visited;
stack<int> topological_order;
void create_topological_order(int node) {
is_visited[node] = true;
int current_nr_neighbors = graph[node].size();
for (int i = 0; i < current_nr_neighbors; ++i) {
if (!is_visited[graph[node][i]]) {
create_topological_order(graph[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_arcs; ++i) {
int source_node, destination_node;
fin >> source_node >> destination_node;
graph[source_node].push_back(destination_node);
}
for (int i = 1; i <= nr_nodes; ++i) {
if (!is_visited[i]) {
create_topological_order(i);
}
}
print_topological_order();
return 0;
}