Cod sursa(job #296625)

Utilizator petrecgClinciu Glisca Petre petrecg Data 4 aprilie 2009 22:59:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <stdio.h>
long n,m,i,j,l,k,x,y,st[50001],a[3][100001],fin[50001],c[50001],deg[50001];
int main()
{freopen("sortaret.in","r",stdin);freopen("sortaret.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for(i=1;i<=m;i++)
  {scanf("%ld%ld",&x,&y);deg[y]++;
   if(fin[x]==0){st[x]=fin[x]=l+1;l++;a[1][l]=y;}
	  else{a[2][fin[x]]=l+1;fin[x]=l+1;l++;a[1][l]=y;}
  }
 l=0;
 for(i=1;i<=n;i++)if(deg[i]==0){l++;c[l]=i;}
 k=1;
 while(k<=l)
  {x=st[c[k]];
   while(x){deg[a[1][x]]--;if(deg[a[1][x]]==0){l++;c[l]=a[1][x];}x=a[2][x];}
   k++;
  }
 for(i=1;i<=l;i++)printf("%ld ",c[i]);
 fclose(stdin);fclose(stdout);
 return 0;
}