Cod sursa(job #159677)

Utilizator ghitza_2000Stefan Gheorghe ghitza_2000 Data 14 martie 2008 12:19:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 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 );   
        
}