Cod sursa(job #651429)

Utilizator juliussSimion Stefan juliuss Data 20 decembrie 2011 13:58:58
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50005

typedef struct nod
{
	int vf;
	struct nod *next;
}Nod;

Nod *L[MAXN];
int n, m, viz[MAXN], postordine[MAXN], len;

void DF(int);

int
main(void)
{
	int i, x, y;
	Nod *p;

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for(i = 1; i <= m; i++)
	{
		scanf("%d %d", &x, &y);
		p = (Nod *) calloc(1, sizeof(Nod));
		p -> vf = y;
		p -> next = L[x];
		L[x] = p;
	}

	for(i = 1; i <= n; i++)
		if(viz[i] == 0)
			DF(i);

	for(i = n; i > 0; i--)
		printf("%d ", postordine[i]);

	return 0;
}

void
DF(int x)
{
	Nod *q;
	viz[x] = 1;

	q = (Nod *) calloc(1, sizeof(Nod));

	for(q = L[x]; q != NULL; q = q -> next)
		if(viz[q -> vf] == 0)
			DF(q -> vf);
	
	postordine[++len] = x;
}