Pagini recente » Borderou de evaluare (job #156782) | Cod sursa (job #223381) | Cod sursa (job #388498) | Cod sursa (job #437577) | Cod sursa (job #2914657)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#define MAX_SIZE 50001
using namespace std;
vector<int> dag[MAX_SIZE];
bitset<MAX_SIZE> is_visited;
stack<int> topological_order;
void create_topological_order(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]]) {
create_topological_order(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_arcs; ++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]) {
create_topological_order(i);
}
}
print_topological_order();
return 0;
}