Cod sursa(job #419851)

Utilizator yrarBogdan Ionut yrar Data 18 martie 2010 08:22:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#define MAX_N 50001

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

void adaug(int i, int j);
void citeste_graf();
void DF(int nod);

struct lista
{
   int nod;
   lista *urm;
} *G[MAX_N];

long N, M, ST[MAX_N], nst;
char U[MAX_N];

void adaug(int i, int j)
{
   lista *p;
   p = new lista;
   p -> nod = j;
   p -> urm = G[i];
   G[i] = p;
}

void citeste_graf()
{
   int i, j;
   f >> N >> M;
   for(; M>0; M--)
   {
      f >> i >> j;
      adaug(i, j);
   }
}

void DF(int nod)
{
   lista *p;
   U[nod]=1;
   for(p = G[nod]; p != NULL; p = p->urm)
      if(!U[p->nod])
         DF(p->nod);
   ST[nst++] = nod;
}

int main()
{
   int i;
   citeste_graf();
   for(i = 1; i <= N; i++)
     if(!U[i]) DF(i);
   for(i = N-1; i>=0; i--)
     g << ST[i] << " ";
}