Cod sursa(job #160421)

Utilizator marinaMarina Horlescu marina Data 15 martie 2008 16:13:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
//Sortare topologica
#include <stdio.h>
#define INPUT "sortaret.in"
#define OUTPUT "sortaret.out"
#define NMAX 50001
#define MMAX 100001

int N, M;

int viz[NMAX], q[NMAX];
int t;

struct nod
{
	nod* leg;
	int vec;
}*graf[NMAX];

void afis()
{
	int i;
	for(i = N; i>1; --i)
		printf("%d ", q[i]);
	printf("%d\n", q[1]);
}

void DF(int src)
{
	viz[src] = 1;
	nod* l;
	for(l = graf[src]; l; l = l->leg)
		if(!viz[l->vec]) 
			DF(l->vec);
	viz[src] = ++t;
}

void solve()
{
	int i;
	for(i = 1; i <= N; ++i)
		if(!viz[i])
			DF(i);
	for(i = 1; i <= N; ++i)
		q[viz[i]] = i;
}

void citire()
{
	scanf("%d %d", &N, &M);
	int i;
	for(i = 1; i <= M; ++i)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		nod *l = new nod;
		l -> vec = b;
		l -> leg = graf[a];
		graf[a] = l;
	}
}


int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
		
	citire();
	solve();
	afis();
	return 0;
}