Cod sursa(job #2079121)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 30 noiembrie 2017 16:27:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#define NMAX 50005
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int n, m, viz[NMAX];
struct nod
{
    int vf;
    nod *next;
} *L[NMAX], *sol;

void add(int a, int b)
{
    nod *p = new nod;
    p->vf = b;
    p->next = L[a];
    L[a] = p;
}

void citire()
{
    in >> n >> m;
    for(int x, y; m; --m)
    {
        in >> x >> y;
        add(x, y);
    }
}

void build_sol(int k)
{
    nod *p = new nod;
    p->vf = k;
    p->next = sol;
    sol = p;
}

void DF(int k)
{
    viz[k] = 1;
    for(; L[k]; L[k] = L[k]->next)
        if(!viz[L[k]->vf])
            DF(L[k]->vf);
    build_sol(k);
}

void sortare_topologica()
{
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            DF(i);
}

void afisare()
{
    while(sol)
    {
        out << sol->vf << ' ';
        sol = sol->next;
    }
}

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