Cod sursa(job #866958)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 ianuarie 2013 22:01:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <cstdio>

#define ALB 0
#define GRI 1
#define NEGRU 2

#define Nmax 50001

using namespace std;

struct nod{

    int vecin;
    nod *next;
};

nod *Graf[Nmax];
nod *lista;

int culori[Nmax];

int N, M;

void citire();
void adauga(int,int);
void pune(int);
void df(int);
void sortare();
void afis();

int main(){

    citire();
    sortare();
    afis();

    return 0;
}

void citire(){

    freopen("sortaret.in", "r", stdin);

    scanf("%d%d", &N, &M);

    for(; M; M--){

        int a, b;

        scanf("%d%d", &a, &b);
        adauga(a, b);
    }
}

void adauga(int a, int b){

    nod *c = new nod;

    c->vecin = b;
    c->next = Graf[a];
    Graf[a] = c;
}

void pune(int a){

    nod * c = new nod;

    c->vecin = a;
    c->next = lista;
    lista = c;
}

void df(int a){

    culori[a] = GRI;

    for( nod * P = Graf[a]; P; P = P->next )
        if(culori[P->vecin] == ALB)
            df(P->vecin);

    culori[a] = NEGRU;
    pune(a);
}

void sortare(){

    for(int i = 1; i <= N; i++)
        if(culori[i] == ALB)
            df(i);
}

void afis(){

    freopen("sortaret.out", "w", stdout);

    for( nod * P = lista; P; P = P->next )
        printf("%d ", P->vecin);
}