Cod sursa(job #150727)

Utilizator a7893Nae Mihai a7893 Data 7 martie 2008 12:12:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#define N 50001
#define M 100001
int n,m,*a[N],niv[N],dg[N],c[N],k;
struct vec{
	int x,y;
}v[M];
void read()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&v[i].x,&v[i].y);
		niv[v[i].x]++;
		dg[v[i].y]++;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=new int[niv[i]+1];
		a[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		a[v[i].x][++a[v[i].x][0]]=v[i].y;
		if(dg[i]==0)
			c[++k]=i;
	}
}
void solve()
{
	int i,j,x,y;
	for(i=1;i<=k;i++)
	{
		x=c[i];
		for(j=1;j<=a[x][0];j++)
		{
			y=a[x][j];
			dg[y]--;
			if(dg[y]==0)
				c[++k]=y;
		}
	}
	for(i=1;i<=k;i++)
		printf("%d ",c[i]);
}
int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	read();
	solve();
	return 0;
}