Cod sursa(job #2182623)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 22 martie 2018 15:41:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <array>
#include <vector>
#include <stack>
#include <iostream>

std::ofstream g("sortaret.out");

int numNodes, numArcs;

std::array<std::vector<int>, 50001> graph;
std::vector<bool> visited(50001, false);
std::stack<int> finalSort;

void Read()
{
	std::ifstream f("sortaret.in");

	f >> numNodes >> numArcs;

	int node1, node2;

	for (int i = 1; i <= numArcs; ++i) {
		f >> node1 >> node2;

		graph[node1].emplace_back(node2);
	}
}

void DFS(int source)
{
	visited[source] = true;

	for (const auto& neighbour : graph[source]) {
		if (!visited[neighbour]) {
			visited[neighbour] = true;
			DFS(neighbour);
		}
	}

	finalSort.emplace(source);
}

int main(int argc, char * argv[])
{
	Read();

	for (int i = 1; i <= numNodes; ++i) {
		if (!visited[i]) {
			DFS(i);
		}
	}

	while (!finalSort.empty()) {
		g << finalSort.top() << ' ';

		finalSort.pop();
	}

	return 0;
}