Cod sursa(job #3232124)

Utilizator ChopinFLazar Alexandru ChopinF Data 29 mai 2024 00:04:49
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
// Folositi neovim pls
#include <bits/stdc++.h>
#include <vector>

using namespace std;

std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
std::vector<int>beenThere , sortareTopologica;
std::vector<std::vector<int>>gf;

int n , m;
void dfs(int node){
	beenThere[node] = 1;
	for(const auto& nextNode : gf[node]){
		if(!beenThere[nextNode]){
			dfs(nextNode);
		}
	}
	sortareTopologica.emplace_back(node);
}
int main(){
	fin >> n >> m;
	beenThere.resize(n + 1);
	gf.resize(n + 1 , std::vector<int>(n + 1));
	for(int i = 0 ; i < m ; ++i){
		int x , y;
		fin >> x >> y;
		gf[x].push_back(y);
	}

	for(int i = 1 ; i <= n ; ++i){
		if(!beenThere[i]){
			dfs(i);
		}
	}
	for(int i = n - 1 ; i >= 0 ; i--){
		fout << sortareTopologica[i] << " ";
	}
}