Cod sursa(job #397607)

Utilizator BooZZySandu Bogdan BooZZy Data 17 februarie 2010 11:06:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
int n,m,x,y,i,v[50005],c[50005],k,viz[50005];
struct nod
{
	int inf;
	nod *adr;
};
nod *l[100000],*p,*d;

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		p=new nod;
		p->adr=l[x];
		p->inf=y;
		l[x]=p;
		v[y]++;
	}
	k=1;
	for(i=1;i<=n;i++)
	{
		if(!v[i])
		{
			c[k++]=i;
			viz[i]=1;
		}
	}
	int pp=1;
	for(;pp<k;pp++)
	{
		d=l[c[pp]];
		while(d)
		{
			v[d->inf]--;
			if(!viz[d->inf]&&v[d->inf]==0)
			{
				c[k++]=d->inf;
				viz[d->inf]=1;
			}
			d=d->adr;
		}
	}
	for(i=1;i<k;i++)
		printf("%d ",c[i]);
	return 0;
}