Cod sursa(job #145115)

Utilizator MarquiseMarquise Marquise Data 28 februarie 2008 14:05:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>

#define NMAX 50001

struct nod
{
	int info;
	nod *next;
};

nod *s[NMAX];

int p[NMAX], n, m;


void adaug(int x, int y)
{
	nod *aux;
	if ( s[x] == NULL)
	{
		s[x] = new nod;
		s[x] -> info = y;
		s[x] -> next = NULL;
	}
	else
	{
		aux = new nod;
		aux -> info = y;
		aux -> next = s[x];
		s[x] = aux;
	}

}

int main()
{
	int i, x, y, ex = 1;
	nod *l;

	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[y]++;
		adaug(x, y);
	}
	while ( ex )
	{
		ex = 0;
		for ( i = 1; i <= n; i++)
			if ( p[i] == 0)
			{
				printf("%d ", i);
				p[i] = -1;
				for ( l = s[i]; l; l = l -> next)
					p[l->info]--;
				ex = 1;
			}
	}


	return 0;
}