Cod sursa(job #2296437)

Utilizator q1e123Solca Robert-Nicolae q1e123 Data 4 decembrie 2018 17:55:02
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include<cstdio>
#include<climits>
#include<vector>

#define pb push_back
#define N_MAX 50001
#define CLEAN 0
#define MARK_TEMPORARY 1
#define MARK_PERMANENT 2

using std::vector;

vector<long> graph[N_MAX], stack;
int mark[N_MAX];
long numberOfNodes,numberOfEdges;

void read(){
	freopen("sortaret.in","r",stdin);
	
	scanf("%ld %ld",&numberOfNodes,&numberOfEdges);
	for(long i=1;i<=numberOfEdges;++i){
		long start,end;
		scanf("%ld %ld",&start,&end);
		graph[start].pb(end);
	}
}

void write(){
	freopen("sortaret.out","w",stdout);
	while(!stack.empty()){
		printf("%ld ",stack.back());
		stack.pop_back();
	}
}

void visit(long data){
	mark[data] = MARK_TEMPORARY;
	for(auto i:graph[data]){
		if(mark[i]==CLEAN) visit(i);
	}
	mark[data] = MARK_PERMANENT;
	stack.pb(data);
}

void sort(){
	for(long i=1;i<=numberOfNodes;++i){
		if(mark[i] == CLEAN) visit(i);
	}
}

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