Cod sursa(job #265602)

Utilizator peanutzAndrei Homorodean peanutz Data 24 februarie 2009 09:25:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#define NMAX 50010

typedef struct nod
{
	int v;
	nod *urm;
} *pnod;
pnod list[NMAX];

int n, m, grad[NMAX];

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

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

void bf()
{
	int inc = 1, sf = 0;
	int c[NMAX], next;
	pnod it;
	int i, x;
	for(i = 1; i <= n; ++i)
		if(!grad[i])
			c[++sf] = i;

	while(inc <= sf)
	{
		x = c[inc++];
		printf("%d ", x);
		for(it = list[x]; it != NULL; it = it -> urm)
		{
			next = it -> v;
			if(--grad[next] == 0)
				c[++sf] = next;
		}
	}
}


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

	read();

	bf();

	return 0;
}