Cod sursa(job #2791943)

Utilizator andreea.ioanaSora Andreea-Ioana andreea.ioana Data 31 octombrie 2021 14:45:47
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

class Graf
{
   private:
       int nrN, nrM; ///Numar noduri, numar muchii
       vector <vector<int>> listaAd; ///lista de adiacenta graf
   public:
       Graf(int, int, vector <vector<int>> &);
       ~Graf();
       void afisare(ostream&);
       friend ostream& operator<<(ostream& out, Graf &g); ///supraincarcare operator <<
       void sortareTopologica(ostream&, int []);
};

Graf :: Graf(int nrNoduri, int nrMuchii, vector <vector<int>> &lista)
{
     nrN = nrNoduri;
     nrM = nrMuchii;
     listaAd = lista;
}

Graf :: ~Graf()
{
    nrN = 0;
    nrM = 0;
    listaAd.clear();
}

void Graf :: afisare(ostream &out)
{
    out << "Numar de noduri: " << nrN << "\n";
    out << "Numar de muchii: " << nrM << "\n";
    for (int i = 0; i < nrN; i++)
        for (int j = 0; j < listaAd[i].size(); j++)
           {
               out << "Muchia "  << i << " " << listaAd[i][j];
               out << "\n";
           }
}

ostream& operator<<(ostream& out, Graf &g)
{
    g.afisare(out);
    return out;
}

void Graf :: sortareTopologica(ostream &out, int grade[])
{
    queue <int> coada;
    vector <int> rez;
    for (int i = 1; i <= nrN; i++)
        if (grade[i] == 0)
            coada.push(i);
    while (!coada.empty())
    {
        int nod_curent = coada.front();
        rez.push_back(nod_curent);
        coada.pop();
        for (int i = 0; i < listaAd[nod_curent].size(); i++)
        {
            int vecin = listaAd[nod_curent][i];
            grade[vecin]--;
            if (grade[vecin] == 0)
                coada.push(vecin);
        }
    }
    for (int i = 0; i < rez.size(); i++)
        out << rez[i] << " ";
}

int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    int n, m, st, dr, grade[50001] = {0};
    fin >> n >> m;
    vector <vector<int>> listaAd (n + 1);
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr;
        listaAd[st].push_back(dr);
        grade[dr]++;
    }
    Graf g(n, m, listaAd);
    g.sortareTopologica(fout, grade);
    fin.close();
    fout.close();
    return 0;
}