Cod sursa(job #502966)

Utilizator igsifvevc avb igsi Data 20 noiembrie 2010 22:51:18
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
using namespace std;

#define IN "sortaret.in"
#define OUT "sortaret.out"


struct Graf{ int nod;Graf *urmator;} **graf, *rezultat;
int *vizit, n;

void citire();
void add(int, int);
void push(int);
void df(int);
void sortaret();
void afisare();

int main()
{
    sortaret();
    afisare();
    return 0;
}

void afisare()
{
    ofstream fout(OUT);
    for(Graf *c = rezultat; c; c = c->urmator)
        fout<<c->nod<<' ';
    fout<<'\n';
    fout.close();
}

void sortaret()
{
    for(int i = 1; i <= n; i++)
        if(vizit[i])
            df(i);
}

void df(int i)
{
    vizit[i] = 0;
    for(Graf *c = graf[i]; c; c = c->urmator)
        if(vizit[c->nod])
            df(c->nod);
}

void push(int i)
{
    Graf *c = new Graf;
    c->nod = i;
    c->urmator = rezultat;
    rezultat = c;
}

void add(int i, int j)
{
    Graf *c = new Graf;
    c->nod = j;
    c->urmator = graf[i];
    graf[i] = c;
}

void citire()
{
    ifstream fin(IN);

    fin>>n;
    rezultat = NULL;
    graf = new Graf*[n+1];
    vizit = new int [n+1];
    for(int i = 0; i <= n; i++) graf[i] = NULL, vizit[i] = 1;

    int m, x, y;
    fin>>m;
    for(int i = 0; i < m; i++)
    {
        fin>>x>>y;
        add(x, y);
    }
    fin.close();
}