Cod sursa(job #237159)

Utilizator crawlerPuni Andrei Paul crawler Data 29 decembrie 2008 01:53:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>

typedef struct X { int a; X *x;} *pX;

#define Nmax 50112

pX l[Nmax];
int n,m, gi[Nmax], gx[Nmax], q[Nmax];
char v[Nmax];

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    
    scanf("%d%d", &n,&m);
    
    int x,y;    
    
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d", &x,&y);
        pX q = new X;
        q->a = y;
        q->x = l[x];
        l[x] = q;
        ++gi[y]; ++gx[x];
    }
    
    int st=1,dr=0;
    
    for (int i=1;i<=n;++i) if (gi[i] == 0) 
    {
        q[++dr] = i;
        v[i] = 1;
        printf("%d ", i);
    }
    
    int nod;
    
    while (st <= dr)
    {
          nod = q[st++];
          for (pX it=l[nod];it;it=it->x)
          {
              --gi[it->a];
              if (gi[it->a] == 0 && v[it->a] == 0) 
              {
                 q[++dr] = it->a;
                 v[it->a] = 1;              
                 printf("%d ", it->a);
              }    
          }
    }   
    
    return 0;    
}