Cod sursa(job #328742)

Utilizator crisojogcristian ojog crisojog Data 3 iulie 2009 11:43:37
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
long x;
long v[50010][5010],cp[1010],q[1010],p,u;
long part(long st, long dr)
{
 long i,j,pivot,aux,m;
 m=(st+dr)/2;
 pivot=v[x][m];
 i=st-1;j=dr+1;
 while(1)
 {
  do{++i;} while(v[x][i]<pivot);
  do{--j;} while(v[x][j]>pivot);
  if(i<j)
  {
   aux=v[x][i];
   v[x][i]=v[x][j];
   v[x][j]=aux;
  }
  else return j;
 }
}
void quicks(long st, long dr)
{
 long p;
 if(st<dr)
 {
  p=part(st,dr);
  quicks(st,p);
  quicks(p+1,dr);
 }
}
void lee()
{
 p=1;
 long i;
 while(p<=u)
 {
  for(i=1;i<=v[q[p]][0];++i)
  {
   cp[v[q[p]][i]]--;
   if(cp[v[q[p]][i]]==0) {u++;q[u]=v[q[p]][i];}
  }
  p++;
 }
}
int main()
{
 long n,r,i,x1,x2;
 freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
 scanf("%ld%ld",&n,&r);
 for(i=1;i<=r;++i)
 {
  scanf("%ld%ld",&x1,&x2);
  
   v[x2][0]++;v[x2][v[x2][0]]=x1;
   cp[x1]++;
 
 }
 for(x=1;x<=n;++x)
  quicks(1,v[x][0]);
 u=0;
 for(i=1;i<=n;++i)
  if(cp[i]==0) {++u;q[u]=i;}
 lee();
 if(u<n) printf("0\n");
 else
 {
  for(i=n;i>=1;--i) printf("%ld ",q[i]);
  printf("\n");
 }
 return 0;
}