Cod sursa(job #2369077)

Utilizator puzzleFlutur Vasile puzzle Data 5 martie 2019 21:00:21
Problema Sortare topologica Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");

const int Nmax = 50000;

class Graph
{
private:
	int m_vertices;
	std::vector<int>V[Nmax];
public:
	Graph(int vertices)
		: m_vertices(vertices)
	{
		for (int i = 1; i <= vertices; i++)
			V[i].reserve(vertices);
	}
	void AddEdge(int where, int what)
	{
		V[where].push_back(what);
	}
	void Print()
	{
		std::vector<int>::iterator it;
		for (int i = 1; i <= m_vertices; i++)
		{
			out << i << ": ";
			for (it = V[i].begin(); it != V[i].end(); it++)
			{
				out << (*it) << " ";
			}
			out << '\n';
		}
	}
	void TopologicalSort();
	void TopSortUtility(int vertex, std::stack<int>& Stack, bool Visited[]);
};

void Graph::TopSortUtility(int vertex, std::stack<int>& Stack, bool Visited[])
{
	Visited[vertex] = true;
	std::vector<int>::iterator i;

	for (i = V[vertex].begin(); i != V[vertex].end(); i++)
	{
		if (!Visited[*i])
			TopSortUtility(*i, Stack, Visited);
	}

	Stack.push(vertex);
}

void Graph::TopologicalSort()
{
	std::stack<int> Stack;
	
	bool* Visited = new bool[m_vertices];
	for (int i = 1; i <= m_vertices; i++)
	{
		Visited[i] = false;
	}

	for (int i = 1; i <= m_vertices; i++)
	{
		if (!Visited[i])
			TopSortUtility(i, Stack, Visited);
	}

	while (!Stack.empty())
	{
		out << Stack.top() << " ";
		Stack.pop();
	}
}

int main()
{
	int n, m;
	in >> n >> m;

	Graph G(n);
	int v1, v2;
	for (int i = 0; i < m; i++)
	{
		in >> v1 >> v2;
		G.AddEdge(v1, v2);
	}
	G.TopologicalSort();
	//G.Print();
}