Cod sursa(job #419009)

Utilizator za_wolfpalianos cristian za_wolf Data 16 martie 2010 20:28:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
#define NMAX 50100
#define MMAX 100100
int q[NMAX],*x[NMAX],nr[NMAX],deg[NMAX],nod,k,i,j,n,m,in,sf;
struct kkt
{
	int X,Y;
} y[MMAX];
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",&y[i].X,&y[i].Y);
		deg[y[i].Y]++;
		nr[y[i].X]++;
	}
	for (i=1;i<=n;i++)
	{
		x[i]= new int [nr[i] +2];
		x[i][0]=0;
		if (deg[i]==0)
			q[++sf]=i;

	}
	for (i=1;i<=m;i++)
		x[y[i].X][++x[y[i].X][0]]=y[i].Y;
	in=1;
	while (in<=sf)
	{
		k=q[in];
		for (i=1;i<=x[k][0];i++)
		{
			nod=x[k][i];
			deg[nod]--;
			if (deg[nod]==0)
				q[++sf]=nod;
		}
		in++;
	}
	for (i=1;i<=n;i++)
		printf("%d ",q[i]);
	printf("\n");




	return 0;
}