Cod sursa(job #281893)

Utilizator za_wolfpalianos cristian za_wolf Data 16 martie 2009 10:44:30
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#define NMAX 50000
#define MMAX 100000
int *x[NMAX];
struct kkt
{
	int A,B;
} q[MMAX];
int y[NMAX],z[NMAX],e[NMAX],w[NMAX],i,j,n,m,k,l,a,s;
int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].A,&q[i].B);
		y[q[i].A]++;
		z[q[i].B]++;
	}
	for (i=1;i<=n;i++)
	{
		x[i]=new int[y[i]+2];
		x[i][0]=0;
	}
	for (i=1;i<=m;i++)
		x[q[i].A][++w[q[i].A]]=q[i].B;

	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
			if (z[j]<=0&&!e[j])
			{
				w[++w[0]]=j;
				e[j]=1;
				for (l=1;l<=y[j];l++)
					z[x[j][l]]--;
			}
	}

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

	return 0;
}