Cod sursa(job #1641159)

Utilizator StanescuVictorStanescu Victor Laurentiu StanescuVictor Data 8 martie 2016 21:18:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
// Infoarena DFS

#include <fstream>
#include <vector>
#include <stack>

std::vector<std::vector<int>> graph;
std::vector<bool> visited;
std::stack<int> topSort;
int vertices, edges;

void topologicalSort(int vertex)
{
	visited[vertex] = true;

	for (int i = 0; i < graph[vertex].size(); i++)
		if (!visited[graph[vertex][i]])
			topologicalSort(graph[vertex][i]);

	topSort.push(vertex);
}

int main()
{
	std::ifstream f("sortaret.in");
	f >> vertices >> edges;
	graph.resize(vertices + 1);
	visited.resize(vertices + 1, false);

	for (int i = 0; i < edges; i++)
	{
		int x, y;
		f >> x >> y;
		graph[x].push_back(y);
	}

	for (int i = 1; i < visited.size(); i++)
		if (!visited[i])
			topologicalSort(i);

	std::ofstream g("sortaret.out");
	while (!topSort.empty())
	{
		g << topSort.top() << " ";
		topSort.pop();
	}

	return 0;
}