Cod sursa(job #2976461)

Utilizator the_horoHorodniceanu Andrei the_horo Data 9 februarie 2023 11:02:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <forward_list>
#include <fstream>
#include <vector>

bool viz[50000];
std::vector<int> edges[50000];

void dfs (int nod, std::forward_list<int> &result) {
	viz[nod] = true;

	for (auto to: edges[nod])
		if (!viz[to])
			dfs(to, result);

	result.emplace_front(nod);
}

int main () {
	std::ifstream in("sortaret.in");
	in.exceptions(std::ifstream::failbit);
	std::ofstream out("sortaret.out");
	out.exceptions(std::ofstream::failbit);

	int n, m;
	in >> n >> m;

	std::forward_list<int> result;


	for (int i = 0; i < m; ++ i) {
		int x, y;
		in >> x >> y;
		-- x, -- y;

		edges[x].emplace_back(y);
	}

	for (int i = 0; i < n; ++ i) {
		if (!viz[i])
			dfs(i, result);
	}

	for (auto nod: result)
		out << nod + 1 << ' ';
}