Cod sursa(job #2370218)

Utilizator puzzleFlutur Vasile puzzle Data 6 martie 2019 11:12:42
Problema Sortare topologica Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb

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

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

class Graph
{
private:
	int m_vertices;
	std::vector<std::vector<int>>V;
public:
	Graph(int vertices)
		: m_vertices(vertices)
	{
        V.resize(m_vertices+1);
	}
	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;
	int i;

	for (i = 0; i < V[vertex].size(); i++)
	{
		if (!Visited[V[vertex][i]])
			TopSortUtility(V[vertex][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();
}