Cod sursa(job #144040)

Utilizator TabaraTabara Mihai Tabara Data 27 februarie 2008 09:04:37
Problema Sortare topologica Scor Ascuns
Compilator cpp Status done
Runda Marime 1.24 kb
#include <stdio.h>

#define ALB 0
#define GRI 1 
#define NEGRU 2

typedef struct nod {
        int vf;
        nod * next;
} *PNOD, NOD;

PNOD L[5005];
PNOD adresa;
int color[5005];
int N, M;

void Read();
void DF(int);
void Push(int);
void Add( int i, int j);
void Write();

int main()
{
    Read();
    
    int i;
    for ( i = 1; i <= N; ++i )
        if ( color[i] == ALB ) 
           DF( i );
    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 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 );
}