Cod sursa(job #2293045)

Utilizator q1e123Solca Robert-Nicolae q1e123 Data 30 noiembrie 2018 14:25:12
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include<cstdio>

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

struct node{
	long data;
	node *next;
};

node *graph[N_MAX],*listSortedElements;

int mark[N_MAX];
long numberOfNodes,numberOfEdges;

void createNode(int data,node *nextElement){	
	node *newNode= new node;
	newNode->data = data;
	newNode->next = nextElement;
	nextElement=newNode;
}

void add(int start,int end){	
	node *newNode= new node;
	newNode->data = end;
	newNode->next = graph[start];
	graph[start] = newNode;
}

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);
		add(start,end);
	}
}

void write(){
	freopen("sortaret.out","w",stdout);
	for(node *i = listSortedElements;i;i=i->next) printf("%d ",i->data);
}

void push(long data){
	node *newNode= new node;
	newNode->data = data;
	newNode->next = listSortedElements;
	listSortedElements = newNode;
}

void visit(long data){
	mark[data] = MARK_TEMPORARY;
	for(node* i=graph[data];i;i = i->next){
		if(mark[i->data] == CLEAN) visit(i->data);
	}
	mark[data] = MARK_PERMANENT;
	push(data);
}

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

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