Cod sursa(job #2574694)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 6 martie 2020 08:53:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n, m;
vector<int> gra[50041];
bool nostart[50041];
void read(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b;
		fin >> a >> b;
		gra[a].push_back(b);
		nostart[b] = true;
	}
}

bool vi[50041];
stack<int> s;
void dfs(int a){
	vi[a] = true;
	for(auto b : gra[a]){
		if(!vi[b]){
			dfs(b);
		}
	}
	s.push(a);
}

void write(){
	while(!s.empty()){
		fout << s.top() << " ";
		s.pop();
	}
}

void topological(){
	for(int i = 1; i <= n; ++i){
		if(!nostart[i]){
			dfs(i);
		}
	}
}

int main(){
	read();
	topological();
	write();
	return 0;
}