Cod sursa(job #2797784)

Utilizator Pop_MariaPop Maria Pop_Maria Data 10 noiembrie 2021 16:34:31
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

class Graf
{
private:

    int numar_noduri, numar_muchii;
    vector <int> lista_adiacenta[10001];

public:

    void sortare_topologica();
    void citire();
    void functie(int nod, int vizitare[], stack <int> &stiva);
};

/// citire
void Graf :: citire()
{
    int capat_stang, capat_drept;

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
    }
}

/// sortare topologica
void Graf :: sortare_topologica()
{
    stack <int> stiva;
    int vizitare[numar_noduri + 1] = {0};

    for(int i = 1; i <= numar_noduri; i++)
        if(!vizitare[i])
            functie(i, vizitare, stiva);

    while(!stiva.empty())
    {
        fout << stiva.top() << " ";
        stiva.pop();
    }
}

/// functie
void Graf :: functie(int nod, int vizitare[], stack <int> &stiva)
{
    vizitare[nod] = 1;

    for(int i = 0; i < lista_adiacenta[nod].size(); i++)
        if(!vizitare[lista_adiacenta[nod][i]])
            functie(lista_adiacenta[nod][i], vizitare, stiva);
    stiva.push(nod);

}

int main()
{
    Graf x;
    x.citire();
    x.sortare_topologica();

    fin.close();
    fout.close();

    return 0;
}