Cod sursa(job #144206)

Utilizator TabaraTabara Mihai Tabara Data 27 februarie 2008 12:41:47
Problema Sortare topologica Scor Ascuns
Compilator cpp Status done
Runda Marime 1.4 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 );
     
}