Cod sursa(job #300131)

Utilizator bacerandreiBacer Andrei bacerandrei Data 7 aprilie 2009 11:42:37
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
#define max 50005

struct nod
{
  int info;
  nod *urm;
} *g[max];

long n, m, st[max], k, i, j;
int use[max];


void adauga(int i, int j)
{
  nod *p;
  p = new nod; p->info = j;
  p->urm = g[i]; g[i] = p;
}



void df(int nd)
{
  nod *p;
  use[nd] = 1;
   for(p = g[nd] ; p != NULL ; p = p->urm)
     if(use[p->info] == 0)
       df(p->info);
   st[k++] = nd;
}



int main()
{
  freopen("sortaret.in" , "r" , stdin);
  freopen("sortaret.out" , "w" , stdout);
   scanf("%ld%ld" , &n , &m);
    for(i = 1 ; i <= m ; i++)
     {
       scanf("%ld%ld", &i, &j);
       adauga(i, j);
     }
   for(i = 1 ; i <= n ; i++)
     if(!use[i])
       df(i);
   for(i = n-1 ; i >= 0 ; i--)
     printf("%ld ", st[i]);
  return 0;
}