Cod sursa(job #1795011)

Utilizator cjalex13Cioarec Alexandru Marian cjalex13 Data 1 noiembrie 2016 21:43:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#define ALB 0
#define GRI 1
#define NEGRU 2
#define NMAX 50005
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

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

PNOD L[NMAX];
PNOD adresa;
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(){
    f>>N>>M;
    int X,Y;
    for(;M>0;M--){
        f>>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(){
    for(PNOD p = adresa ; p ; p=p->next){
        g<<p->vf<<" ";
    }
}