Cod sursa(job #2914352)

Utilizator george_buzasGeorge Buzas george_buzas Data 19 iulie 2022 17:38:04
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#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;
}