Cod sursa(job #3178014)

Utilizator bombatongaMunteanu David Ioan bombatonga Data 30 noiembrie 2023 19:54:00
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
#include <bitset>

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

const int nMax = 5e4;

std::bitset<nMax> vis;

std::vector<int> sort;

std::vector<std::vector<int>> graph;

void dfs(int node) {
	vis[node] = 1;
	for (int i : graph[node])
		if (!vis[i])
			dfs(i);
	sort.emplace_back(node);
}

int main() {
	int N, M;
	fin >> N >> M;
	graph.assign(N, std::vector<int>());

	for (int i = 1; i <= M; i++) {
		int x, y;
		fin >> x >> y;
		x--; y--;

		graph[x].emplace_back(y);
	}

	for (int i = 0; i < N; i++)
		if (!vis[i])
			dfs(i);

	std::reverse(sort.begin(), sort.end());

	for (int i : sort)
		fout << i + 1 << ' ';

	graph.clear();
	fin.clear(); fout.clear();
	return 0;
}