Cod sursa(job #228039)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 6 decembrie 2008 12:08:35
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<stdio.h>
long n,m,i,a[105000],b[105000],h[105000],s[105000],l[105000],ls,ll,x,inc[105000],sf[105000];
int main()
{
 freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
 scanf("%ld%ld",&m,&n);
 for(i=1;i<=n;++i)
    {scanf("%ld%ld",&a[i],&b[i]);++h[b[i]];if(!inc[a[i]])inc[a[i]]=i;sf[a[i]]=i;}
 for(i=1;i<=m;++i)if(h[i]==0)s[++ls]=i;
 while(ls)
 {l[++ll]=x=s[ls];
  --ls;
  for(i=inc[x];i<=sf[x];++i)if(a[i]==x){--h[b[i]];if(h[b[i]]==0)s[++ls]=b[i];}
 }
 for(i=1;i<=ll;++i)printf("%ld ",l[i]);
 printf("\n");
 return 0;
}