Cod sursa(job #2275378)

Utilizator ionutnivIonut Nivaci ionutniv Data 3 noiembrie 2018 09:55:59
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>



#define ALB 0

#define GRI 1

#define NEGRU 2

#define NMAX 50005



typedef struct nod {

        int vf;

        nod * next;

} *PNOD, NOD;



PNOD L[NMAX];//Listele de vecini pentru fiecare nod

PNOD 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()

{

     freopen( "sortaret.in" , "r", stdin );



     scanf( "%d%d", &N, &M );

     int X, Y;

     for ( ; M > 0; M-- )

     {

         scanf( "%d%d", &X, &Y);

         Add(X,Y);

     }

}



void Add( int i, int j)

{

     PNOD p = new NOD;

     p->vf = j;

     p->next = L[i];

     L[i] = p;

}



void S_Topologica()

{

     int i;

     for ( i = 1; i <= N; ++i )

         if ( color[i] == ALB )

            DF( i );

}



void DF( int nod )

{

     color[nod] = GRI;

     for ( PNOD p = L[nod]; p; p = p->next )

         if ( color[p->vf] == ALB )

              DF( p->vf );

     color[nod] = NEGRU;

     Push( nod );

}



void Push( int nod )

{

     PNOD p = new NOD;

     p->vf = nod;

     p->next = adresa;

     adresa = p;

}



void Write()

{

     freopen( "sortaret.out", "w", stdout );

     for ( PNOD p = adresa; p; p = p->next )

         printf( "%d ", p->vf );



}