Cod sursa(job #2154165)

Utilizator KazvikKokovics Razvan Kazvik Data 6 martie 2018 18:59:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#define ALB 0
#define GRI 1
#define NEGRU 2
#define NMAX 50005

using namespace std;

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

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

PNOD L[NMAX];
PNOD adresa;

int color[NMAX];
int n,m;

void listare(int nod){
     PNOD p=new NOD;
     p->vf=nod;
     p->next=adresa;
     adresa=p;
}

void DFS(int nod){
     color[nod]=GRI;
     for(PNOD p=L[nod];p!=NULL;p=p->next)
         if(color[p->vf]==ALB)
              DFS(p->vf);
     color[nod]=NEGRU;
     listare(nod);
}

void S_Topologica(){
     int i;
     for(i=1;i<=n;i++)
         if(color[i]==ALB)
            DFS(i);
}

void adauga(int a, int b){
     PNOD p = new NOD;
     p->vf=b;
     p->next=L[a];
     L[a]=p;
}

void citire(){
     in>>n>>m;
     int x,y;
     for(int i=1;i<=m;i++){
         in>>x>>y;
         adauga(x,y);
     }
}

void afisare(){
     for(PNOD p=adresa;p!=NULL;p=p->next)
         out<<p->vf<<" ";

}

int main(){
    citire();
    S_Topologica();
    afisare();
    return 0;
}