Cod sursa(job #832983)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 11 decembrie 2012 19:37:04
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <list>

#define MAXN 50000 

int N,M,i;

std::list<int> startnodes;
std::list<int> neigh[MAXN];
bool hasincoming[MAXN];
bool visited[MAXN];

int sorted[MAXN];
int sorted_index = 0;


void DFS(int node)
{
	sorted[sorted_index++] = node;
	
	std::list<int>::iterator it;
	for(it = neigh[node].begin(); it != neigh[node].end(); it++){
		if(!visited[*it])
			DFS(*it);		
	}
	
	visited[node] = true;
}

int main(int argc, char* argv[])
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	for(i=0;i<M;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		neigh[a-1].push_front(b-1);
		hasincoming[b-1] = true;
	}
	
	for(i=0;i<N;i++){
		if( !hasincoming[i] )
			startnodes.push_front(i);
	}
	
	std::list<int>::iterator it;
	for(it = startnodes.begin(); it != startnodes.end(); it++){
		DFS(*it);
	}
	
	for(i=0;i<N;i++)
		printf("%d ",sorted[i]+1);
	
	return 0;
}