Cod sursa(job #2790762)

Utilizator Dantelogus99Gruia Gabriel Dantelogus99 Data 29 octombrie 2021 14:45:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <list>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

class Graf
{
    int nrNoduri;
    int nrMuchii;
    bool orientat;

    vector<list<int>> listaAdiacenta;


public:

    Graf(int n, int m, bool o)
    {
        nrNoduri = n;
        nrMuchii = m;
        orientat = o;
        listaAdiacenta.resize(nrNoduri + 1);
    }

    void citireGraf()
    {
        int x, y;
        for (int i = 0; i < nrMuchii; i++)
        {
            fin >> x >> y;
            listaAdiacenta[x].push_back(y);

            if(!orientat)
                listaAdiacenta[y].push_back(x);
        }
    }


    list<int> sortareTopologica()
    {
        list<int> listaTP;
        vector<bool> vizitat(nrNoduri + 1, false);

        for (int i = 1; i <= nrNoduri; i++)
            if (!vizitat[i])
                topologicDFS(i, listaTP, vizitat);

        return listaTP;
    }


private:

    void topologicDFS(int nodS, list<int>& ordine, vector<bool>& vizitat)
    {
        vizitat[nodS] = true;

        for (auto x : listaAdiacenta[nodS])
            if (!vizitat[x])
                topologicDFS(x, ordine, vizitat);

        ordine.push_front(nodS);
    }
};


int main()
{
    int n, m, s;
    fin >> n >> m;

    Graf G(n ,m, true);
    //Graf G(false);

    G.citireGraf();
    //G.afisareGraf();

/* ---> SORTARE TOPOLOGICA <--- */
    list<int> TP = G.sortareTopologica();

    for (auto x : TP)
        fout << x << " ";
}