Cod sursa(job #406193)

Utilizator samuel91Asofronie Samuel samuel91 Data 1 martie 2010 12:16:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala 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 ); 
}