Cod sursa(job #3218173)

Utilizator george_buzasGeorge Buzas george_buzas Data 26 martie 2024 12:36:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#define MAX_NR_NODES 50000
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

bitset<MAX_NR_NODES + 1> isVisited;
vector<int> graph[MAX_NR_NODES + 1];
stack<int> topologicalOrder;

void dfsTopoSort(int node) {
	isVisited[node] = true;
	int nrNeighbours = graph[node].size();
	for (int i = 0; i < nrNeighbours; ++i) {
		int neighbour = graph[node][i];
		if (!isVisited[neighbour]) {
			dfsTopoSort(neighbour);
		}
	}
	topologicalOrder.push(node);
}

void createTopologicalSort(int nrNodes) {
	for (int node = 1; node <= nrNodes; ++node) {
		if (!isVisited[node]) {
			dfsTopoSort(node);
		}
	}
}

void printTopologicalOrdering() {
	while (!topologicalOrder.empty()) {
		fout << topologicalOrder.top() << ' ';
		topologicalOrder.pop();
	}
}

int main() {
	int nrNodes, nrDirectedEdges;
	fin >> nrNodes >> nrDirectedEdges;
	for (int directedEdge = 1; directedEdge <= nrDirectedEdges; ++directedEdge) {
		int sourceNode, destinationNode;
		fin >> sourceNode >> destinationNode;
		graph[sourceNode].push_back(destinationNode);
	}
	createTopologicalSort(nrNodes);
	printTopologicalOrdering();
	return 0;
}