Cod sursa(job #2431723)

Utilizator ShayTeodor Matei Shay Data 20 iunie 2019 17:58:46
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <assert.h>
#include <stack>
#include <vector>
#include <iterator>
#include <iostream>

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

void dfs(int src, std::vector<bool> &visited, std::vector<std::vector<int>> matrix, std::stack<int> &stack) {
	visited[src] = true;

	for (auto it = matrix[src].begin(); it != matrix[src].end(); ++it) {
		if (!visited[*it]) {
			visited[*it] = true;
			dfs(*it, visited, matrix, stack);
		}
	}

	stack.push(src);
}

int main() {
	int n, m, src, dest;
	std::stack<int> stack;
	in >> n >> m;
	assert(1 <= n && n <= 50000);
	assert(1 <= m && m <= 100000);
	std::vector<bool> visited(n + 1, false);
	std::vector<std::vector<int>> matrix (n + 1, std::vector<int>(n + 1));

	for(; m ; --m) {
		in >> src >> dest;
		matrix[src].push_back(dest);
	}

	for (int i = 1 ; i <= n ; ++i) {
		if (!visited[i]) {
			dfs(i, visited, matrix, stack);
		}
	}

	while (!stack.empty()) {
		int node = stack.top();
		stack.pop();
		if (node) out << node << " ";
	}

	in.close();
	out.close();
	return 0;
}