Cod sursa(job #2918105)

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

using namespace std;

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

int no_of_vertices{ 0 };
int no_of_edges{ 0 };
vector<vector<int>> graph(no_of_vertices + 1);
std::stack<int> stackk;
vector<bool> visited_vertices(no_of_vertices + 1);


void topological_sort(int current_vertice)
{
	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[current_vertice][i]);
		}
	}
	stackk.push(current_vertice);
}

void print_stack(std::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() {

	fin >> no_of_vertices;
	fin >> no_of_edges;

	add_edges(graph, no_of_edges);

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

	print_stack(stackk);

	return 0;
}