Cod sursa(job #832993)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 11 decembrie 2012 19:52:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <list>

#define MAXN 50000 

int N,M,i;

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

int sorted[MAXN];
int sorted_index = 0;


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

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[b-1].push_front(a-1);
		hasincoming[a-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;
}