Cod sursa(job #1650452)

Utilizator Vertex10Alexandru Pokharel Vertex10 Data 11 martie 2016 18:25:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#define limM 100001
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int lst[50001], urm[limM], vf[limM], grad_int[50001], nr, n, m, coada[50001], u, p=1;

void parc (int x)
{
    int i = lst[x];
    g << x << " ";
    while (i)
    {
        int y = vf[i];

        --grad_int[y]; //daca y are grad interior 0, adauga-l in coada
        if (grad_int[y]==0)
            coada[++u] = y;

        i = urm[i];
    }
}
void adauga (int x, int y)
{
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
    ++grad_int[y];
}

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

    for (int i=1; i<=n; ++i)
    {
        if (grad_int[i]==0)
            coada[++u] = i;
    }

    while (p<=u)
    {
        parc(coada[p]);
        ++p;
    }
    /*for (int i=1; i<=n; ++i)
        g << lst[i] << " ";
    g << endl;
    for (int i=1; i<=m; ++i)
        g << vf[i] << " ";
    g << endl;
    for (int i=1; i<=m; ++i)
        g << urm[i] << " ";
    g << endl;*/
    return 0;
}