Cod sursa(job #238727)

Utilizator zbarniZajzon Barna zbarni Data 3 ianuarie 2009 00:32:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<stdlib.h>
#define nmax 50005
int *a[nmax],Q[nmax],dx[nmax];
int main()
 {
  freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);
  int i,x,y,n,m;
  scanf("%d%d",&n,&m);
  for (i=1;i<=n;i++)
   {
    a[i]=(int *)realloc(a[i],sizeof(int));
    a[i][0]=0;
   }
  for (i=1;i<=m;++i)
   {
    scanf("%d %d",&x,&y);
    ++a[x][0];
    a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
    a[x][a[x][0]]=y;
    ++dx[y];
   }
  int j;
  for (i=1;i<=n;++i)
   if (!dx[i])
     Q[++Q[0]]=i;
  for (i=1;i<=n;++i)
   {
    x=Q[i];
    for (j=1;j<=a[x][0];++j)
     {
      --dx[a[x][j]];
      if (dx[a[x][j]]==0)
	Q[++Q[0]]=a[x][j];
     }
   }
  for (i=1;i<=Q[0];++i)
    printf("%d ",Q[i]);
  printf("\n");
  return 0;
 }