Cod sursa(job #2786856)

Utilizator andre.anghelacheAndreea Anghelache andre.anghelache Data 21 octombrie 2021 19:27:31
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

const int maxim = 50001;

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

class Graf{
    int noduri, muchii;
    //lista de adiacenta
    vector<int> listaAdiacenta[maxim];
    int gradeInterioare[maxim] = {0};
public:
    Graf(int noduri, int muchii) : noduri(noduri), muchii(muchii) {}
    void construieste(int start, int final);
    void sortareTopologica();
};

void Graf::construieste(int start, int final) {
    listaAdiacenta[start].push_back(final);
    gradeInterioare[final]++;
}

void Graf::sortareTopologica() {
    queue<int> myqueue;

    for(int i = 1; i <= noduri; i++)
        if (gradeInterioare[i] == 0)
        {
            myqueue.push(i);
        }

    while(!myqueue.empty())
    {
        int nodCurent = myqueue.front();

        for(int i = 0; i < listaAdiacenta[nodCurent].size(); i++)
        {
            gradeInterioare[listaAdiacenta[nodCurent][i]]--;
            if(gradeInterioare[listaAdiacenta[nodCurent][i]] == 0)
                myqueue.push(listaAdiacenta[nodCurent][i]);
        }

        myqueue.pop();
        cout << nodCurent << " ";
    }
}

int main() {

    int noduri, muchii, x, y;
    in>>noduri>>muchii;

    Graf mygraf(noduri, muchii);

    for(int i=0; i<muchii; i++)
    {
        in>>x>>y;
        mygraf.construieste(x, y);
    }

    mygraf.sortareTopologica();

    in.close();
    out.close();
    return 0;
}