Cod sursa(job #1456642)

Utilizator petru.cehanCehan Petru petru.cehan Data 1 iulie 2015 14:42:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("sortaret.in") ;
ofstream fout ("sortaret.out") ;

#define NMAX 50001

struct nod
   {
        int info;
        nod * next;
   } ;
nod * L[NMAX] ; //Listele de vecini pentru fiecare nod
nod * adresa ; // lista simplu inlantuita
int color [NMAX];
int N, M;

void Read();
void DF(int);
void Push(int);
void S_Topologica();
void Add( int,int);
void Write();

int main()
{
    Read();
    S_Topologica();
    Write();

    return 0;
}

void Read()
{
     fin >> N >> M ;
     int X, Y;
     for ( ; M >= 1; M-- )
     {
         fin >> X >> Y ;
         Add (X,Y);
     }
}

void Add( int i, int j)
{
     nod * p = new nod;
     p->info = j;
     p->next = L[i];
     L[i] = p;
}

void S_Topologica()
{
     int i;
     for ( i = 1; i <= N; ++i )
         if ( color [i] == 0 )
            DF( i );
}

void DF( int nd )
{
     color [nd] = 1 ;
     for ( nod * p = L[nd]; p ; p = p->next )
         if ( color [p->info] == 0 )
              DF( p->info );
    // color [nd] = 2 ;
     Push ( nd );
}

void Push( int nd )
{
     nod * p = new nod;
     p->info = nd ;
     p->next = adresa;
     adresa = p;
}

void Write()
{
     for ( nod * p = adresa; p; p = p->next )
            fout << p->info << " " ;

}