Cod sursa(job #150269)

Utilizator peanutzAndrei Homorodean peanutz Data 6 martie 2008 20:00:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct nod
{
	long v;
	nod *urm;
} *pnod;

#define NMAX 50010


pnod list[NMAX];
long n, m, grad[NMAX];

inline void baga(long x, long y)
{
	pnod aux;
	aux = new nod;
	aux -> v = y;
	aux -> urm = list[x];
	list[x] = aux;
}

void read()
{
	long i, x, y;
	scanf("%ld %ld", &n, &m);
	while(m--)
	{
		scanf("%ld %ld", &x, &y);
		baga(x, y);
		++grad[y];
	}
}

long c[NMAX];

void bf()
{
	pnod it;
	long x, i, next;
	long inc = 0, sf = 0;

	for(i = 1; i <= n; ++i)
		if(!grad[i]) c[++sf] = i;

	while(inc <= sf)
	{
		x = c[inc++];


		for(it = list[x]; it != NULL; it = it -> urm)
		{
			next = it -> v;
			--grad[next];
			if(!grad[next])
				c[++sf] = next;
		}
	}
}

int main()
{
	long i;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	read();

	bf();

	for(i = 1; i <= n; ++i)
		printf("%ld ", c[i]);


	return 0;
}