Cod sursa(job #144677)

Utilizator cos_minBondane Cosmin cos_min Data 27 februarie 2008 20:54:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "sortaret.in"
#define out "sortaret.out"
#define dim 50001

int N, M;
bool Sel[dim];

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

PNOD graph[dim], Stiva;

void Add(int,int);
void Push(int);
void DF(int);

int main()
{
    int X, Y;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    memset(Sel,0,sizeof(Sel));
    
    scanf("%d%d", &N, &M);
    for ( ; M; M-- )
        scanf("%d%d", &X, &Y), Add(X,Y); 
    
    for ( int i = 1; i <= N; i++ )
        if ( !Sel[i] ) DF(i);
    
    for ( PNOD q = Stiva; q; q=q->next )
        printf("%d ", q->vf);
}

void DF(int nod)
{
     Sel[nod] = 1;
     
     for ( PNOD q = graph[nod]; q; q=q->next )
         if ( !Sel[q->vf] ) DF(q->vf);
     
     Push(nod);
}

void Add( int i, int j)  
{  
      PNOD p = new NOD;  
      p->vf = j;  
      p->next = graph[i];  
      graph[i] = p;  
}  

void Push(int K)
{
     PNOD p = new NOD;
     p->vf = K;
     p->next = Stiva;
     Stiva = p;
}