Cod sursa(job #3312930)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 30 septembrie 2025 20:33:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>

const int32_t MAX_N = 50000;

std::vector<int32_t> adj[MAX_N];
bool used[MAX_N];
int32_t sorted[MAX_N], bot;

void DFS(int32_t node) {
	used[node] = true;

	for(int32_t next : adj[node]) {
		if(!used[next])
			DFS(next);
	}

	sorted[bot--] = node;
}

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

	int32_t n, m;
	fin >> n >> m;

	for(int32_t i = 0; i != m; ++i) {
		int32_t x, y;
		fin >> x >> y;
		--x; --y;

		adj[x].push_back(y);
	}

	bot = n - 1;
	for(int32_t i = 0; i != n; ++i) {
		if(!used[i])
			DFS(i);
	}

	for(int32_t i = 0; i != n; ++i)
		fout << (sorted[i] + 1) << ' ';

	fin.close();
	fout.close();

	return 0;
}