Cod sursa(job #289981)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 27 martie 2009 11:47:19
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
const long NMAX=50010;
const long MMAX=100010;
long *a[NMAX], n, m, d[NMAX], da[NMAX], x[MMAX], y[MMAX], q0[NMAX], q[NMAX], u, p0, u0;
int main()
{
	long i, nod;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<m; i++)
	{
		scanf("%ld%ld", &x[i], &y[i]);
		da[x[i]]++;
		d[y[i]]++;
	}//for i
	for (i=1; i<=n; i++)
	{
		a[i]=new long[da[i]+1];
		a[i][0]=0;
	}//for i
	for (i=0; i<m; i++)
		a[x[i]][++a[x[i]][0]]=y[i];
	for (i=1; i<n; i++)
		if (d[i]==0)
			q0[u0++]=i;
	while (p0<u0)
	{
		q[u++]=q0[p0];
		nod=q0[p0++];
		for (i=1; i<=a[nod][0]; i++)
		{
			d[a[nod][i]]--;
			if (d[a[nod][i]]==0)
				q0[u0++]=a[nod][i];
		}//for i
	}//while
	for (i=0; i<u; i++)
		printf("%ld ", q[i]);
	return 0;
}//main