Cod sursa(job #754321)

Utilizator MarquiseMarquise Marquise Data 1 iunie 2012 17:12:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#define NMAX 50001

struct nod
{
       int info;
       nod *next;
};

nod *s[NMAX];
int p[NMAX], n, m;

void adaug(int suc, int in)
{
     nod *aux;
     
     aux = new nod;
     aux -> info = in;
     
     if (s[suc] == NULL)
     {
         aux -> next = NULL;
     }
     else
     {
         aux -> next = s[suc];
      
     }
     s[suc] = aux;
     
}

int main()
{
    int i, x, y, ex = 1;
    nod *j;
    
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    for ( i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);
        adaug(x,y);
        p[y]++;
    }
    
    while (ex)
    {
          ex = 0;
          for ( i = 1; i <=n; i++)
              if ( p[i] == 0)
              {
                   p[i]--;
                   printf("%d ", i);
                   for ( j = s[i]; j; j = j -> next)
                       p[j -> info]--;
                   ex = 1;    
              }
    }
    
    
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}