Cod sursa(job #2797447)

Utilizator Pop_MariaPop Maria Pop_Maria Data 9 noiembrie 2021 21:56:54
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#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];
    int vizitare[5001];

public:

    void citire();
    void parcurgere();
    void sortare_topologica(int);

};

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

    fin >> numar_noduri >> numar_muchii;

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

/// algoritmul de sortare topologica
void Graf :: sortare_topologica(int nod)
{
    vizitare[nod] = 1;

    for(int i : lista_adiacenta[nod])
        if(!vizitare[i])
            sortare_topologica(i);

    fout << nod << " ";
}

/// parcurgerea
void Graf :: parcurgere()
{
    for(int j = 1; j <= numar_noduri; j++)
        if(!vizitare[j])
            sortare_topologica(j);
}

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

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

    return 0;
}