Cod sursa(job #2202436)

Utilizator MelacasKorian Ebraahim Melacas Data 8 mai 2018 19:26:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.15 kb
#include <iostream>
#include <cstdio>
#include <queue>

#define minInfinit -2000000000

using namespace std;

class minPq
{
    public :

    bool operator() (const int &a, const int &b)
    {
        return a > b;
    }
};

class Vector
{
    public :

    // valori
    int valoare;
    Vector* urm;
    Vector* sfarsit;

    // constructor
    Vector(const int&);

    // functii
    friend ostream& operator<<(ostream&, const Vector&);
    void adauga(const int &x);
};

Vector :: Vector(const int &x)
{
    valoare = x;
    urm = NULL;
    sfarsit = NULL;
}

ostream& operator<<(ostream &out, const Vector &x)
{
    out << x.valoare << " ";

    Vector* p = x.urm;
    while (p)
    {
        out << p->valoare << " ";
        p = p->urm;
    }
    return out;
}

void Vector :: adauga(const int &x)
{
    if (sfarsit)
    {
        while (sfarsit->urm)
            sfarsit = sfarsit->urm;

        Vector* b = new Vector(x);
        sfarsit->urm = b;
        sfarsit = b;
    }
    else
    {
        Vector* b = new Vector(x);
        sfarsit = b;
    }

    if (urm == NULL)
        urm = sfarsit;
}

void df(int &nod, Vector* &sortareTopologica, Vector** &muchii, int* &gradeIntrare, bool* &vizitat)
{
    if (vizitat[nod] == 0)
    {
        vizitat[nod] = 1;
        if (sortareTopologica == NULL)
            sortareTopologica = new Vector(nod + 1);
        else
            sortareTopologica->adauga(nod + 1);

        if (muchii[nod])
        for (Vector* p = muchii[nod] ; p ; p = p->urm)
        {
            gradeIntrare[p->valoare]--;
            if (gradeIntrare[p->valoare] == 0)
                df(p->valoare,sortareTopologica,muchii,gradeIntrare,vizitat);
        }
    }
}

void drumCritic()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    priority_queue <int, vector<int> , minPq> PQ;

    int n(0);
    scanf("%d",&n);

    /*int* drumuri = new int[n];
    for (int i = 0 ; i < n ; i++)
        scanf("%d",&drumuri[i]);*/

    int m(0);
    scanf("%d",&m);

    Vector** muchii = new Vector*[n];
    for (int i = 0 ; i < n ; i++)
        muchii[i] = NULL;

    int *gradeIntrare = new int[n]; // de fiecare data trebuie sa initializez vectorul !
    for (int i = 0 ; i < n ; i++)
        gradeIntrare[i] = 0;
    for (int i = 0 ; i < m ; i++)
    {
        int a(0), b(0);
        scanf("%d %d\n",&a,&b);
        a--;
        b--;
        gradeIntrare[b]++;
        if (muchii[a] == NULL)
            muchii[a] = new Vector(b);
        else
            muchii[a]->adauga(b);
    }

    Vector* sortareTopologica = NULL;
    bool* vizitat = new bool[n];
    for (int i = 0 ; i < n ; i++)
        vizitat[i] = 0;
    for (int i = 0 ; i < n ; i++)
    {
        if (gradeIntrare[i] == 0)
            df(i,sortareTopologica,muchii,gradeIntrare,vizitat);
    }
    if (sortareTopologica)
        cout << *sortareTopologica;
}

///     1. La sortarea topologica, daca alegem DF, de ce trebuie sa adaugam varful de-abia la final,
/// in loc sa il adaugam la inceput ?

int main()
{
    drumCritic();
    return 0;
}