Cod sursa(job #228810)

Utilizator socheoSorodoc Ionut socheo Data 8 decembrie 2008 08:50:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
int g[3][100000],i,j,n,m,st[50000],deg[50000],nr,c[50000],y;
int main()
{ freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);
 scanf("%d%d",&n,&m);
 for(i=1;i<=m;i++)
  {
   scanf("%d%d",&g[1][i],&g[2][i]);
     if(g[1][i]!=g[1][i-1])
      st[g[1][i]]=i;
    deg[g[2][i]]++;
    }
 nr=1;
for(i=1;i<=n;i++)
  if(deg[i]==0)
    c[nr++]=i;
for(i=1;i<=n-1;i++)
  { y=c[i];
    for(j=st[y];g[1][j]==g[1][j-1]||j==st[y];j++)
     { deg[g[2][j]]--;
      if(deg[g[2][j]]==0)
       c[nr++]=g[2][j];
      }
   }
 for(i=1;i<=n;i++)
   printf("%d ",c[i]);
return 0;
}