Cod sursa(job #2773215)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 5 septembrie 2021 16:50:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <forward_list>

const int MAX_N = 50001;
const int MAX_M = 100001;

int n, m;
std::vector<int> graph[MAX_N];
std::forward_list<int> sorted;
bool flag[MAX_N];

void read()
{
	std::ifstream input("sortaret.in");
	input >> n >> m;
	int x, y;
	for (int edge(0); edge < m; ++edge) {
		input >> x >> y;
		graph[x].push_back(y);
	}
	input.close();
}

void print()
{
	std::ofstream output("sortaret.out");
	for (auto it : sorted) {
		output << it << ' ';
	}
	output.put('\n');
	output.close();
}

void dfs(int vertex)
{
	flag[vertex] = true;
	for (auto neighbor : graph[vertex]) {
		if (!flag[neighbor]) {
			dfs(neighbor);
		}
	}
	sorted.push_front(vertex);
}

void toposort()
{
	for (int vertex(1); vertex <= n; ++vertex) {
		if (!flag[vertex]) {
			dfs(vertex);
		}
	}
}


int main()
{
	read();
	toposort();
	print();
	return 0;
}