Cod sursa(job #2918104)

Utilizator vasi_kosminskiHoroi Vasile vasi_kosminski Data 9 august 2022 20:30:55
Problema Sortare topologica Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

void topological_sort(vector<vector<int>> graph, int no_of_vertices, int current_vertice, stack<int>& stack, vector<bool>& visited_vertices)
{
	visited_vertices[current_vertice] = true;

	for (int i = 0; i < graph[current_vertice].size(); i++)
	{
		if (!visited_vertices[graph[current_vertice][i]])
		{
			topological_sort(graph, no_of_vertices, graph[current_vertice][i], stack, visited_vertices);
		}
	}
	stack.push(current_vertice);
}

void print_stack(stack<int> stack)
{
	while (!stack.empty()) {
		fout << stack.top() << " ";
		stack.pop();
	}
}

void add_edges(vector<vector<int>>& graph, int no_of_edges)
{
	int from_vertex{ 0 };
	int to_vertex{ 0 };

	for (int i = 1; i <= no_of_edges; i++)
	{
		fin >> from_vertex >> to_vertex;
		graph[from_vertex].push_back(to_vertex);
	}
}


int main() {
	int no_of_vertices{ 0 };
	int no_of_edges{ 0 };

	fin >> no_of_vertices;
	fin >> no_of_edges;

	vector<vector<int>> graph(no_of_vertices + 1);

	add_edges(graph, no_of_edges);

	stack<int> stack;
	vector<bool> visited_vertices(no_of_vertices + 1);

	for (int i = 1; i <= no_of_vertices; i++)
	{
		if (!visited_vertices[i])
		{
			topological_sort(graph, no_of_vertices, i, stack, visited_vertices);
		}
	}

	print_stack(stack);

	return 0;
}