Cod sursa(job #146546)

Utilizator andrei_infoMirestean Andrei andrei_info Data 1 martie 2008 21:25:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX 50004


typedef struct nod {
		long nr;
		nod* urm;
};

nod* G[MAX];

long gr[MAX], N,M, rez[MAX], nr_rez;
nod *Q_i, *Q_s;

void add( nod *&Q, long nr)
{
	nod* aux = new nod;
	aux->nr= nr;
	aux->urm = Q;
	Q = aux;
}

void add_Q( long nr)
{
	nod* aux = new nod;
	aux->nr = nr;
	aux->urm = NULL;

	if ( Q_s == NULL )
		Q_i = Q_s = aux;
	else
	{
		Q_s->urm = aux;
		Q_s = aux;
	}
}



void solve()
{
	int i;
	Q_i = Q_s = NULL;

	for (i = 1; i<=N; i++)
		if ( gr[i] == 0 )
			add_Q(i);

	nod* aux= Q_i, *it;
	while ( aux != NULL )
	{
		//printf("%ld ", aux->nr);
		rez[nr_rez++] = aux->nr;

		it = G[aux->nr];
		while ( it != NULL )
		{
			gr[it->nr]--;
			if ( !gr[it->nr] )
				add_Q ( it->nr );
			it = it->urm;
		}

		aux = aux->urm;
	}
}


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

	scanf("%ld %ld", &N, &M);

	long a,b;

	for (int i = 1; i<=N; i++)
		G[i] = NULL;

	for ( ; M>0; M--)
	{
		scanf("%ld %ld", &a, &b);

		add(G[b], a);
		gr[a]++;
	}

	solve();

	for (nr_rez--; nr_rez>= 0; nr_rez--)
		printf("%ld ", rez[nr_rez]);



	return 0;
}