Cod sursa(job #1321557)

Utilizator Toast97Calin Farcas Toast97 Data 19 ianuarie 2015 11:59:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>

using namespace std;

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

struct nod
{
    int info;
    nod *adr;
} *v[50005];

void adaugare (int nr, int x)
{
    nod *c;
    c = new nod;

    c -> info = x;
    c -> adr = v[nr];

    v[nr] = c;
}

void sterge (int nr)
{
    nod *p;
    p = v[nr];

    v[nr] = v[nr] -> adr;
    delete p;
}

int n, m, sol[50005], curent = 0;
bool viz[50005];

void citire ()
{
    f >> n >> m;

    int x, y;

    for (int i = 1; i <= m; i ++)
    {
        f >> x >> y;
        adaugare (x, y);
    }
}

void dfs (int nr)
{
    viz[nr] = 1;

    nod *c;

    c = v[nr];

    while (c)
    {
        if (! viz[c -> info])
            dfs (c -> info);

        c = c -> adr;
    }

    sol [++curent] = nr;
}

int main()
{
    citire ();

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

    for (int i = n; i >= 1; i --)
        g << sol[i] << " ";

    f.close ();
    g.close ();
    return 0;
}