Cod sursa(job #2792244)

Utilizator Maria23Dutu Maria Maria23 Data 1 noiembrie 2021 11:35:33
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

using namespace std;

const int NMAX = 50001;
ifstream fin("sortaret.in");
ofstream fout ("sortaret.out");

class graf{
private:
    int nrNoduri, nrMuchii;
    vector<int> listaAd[NMAX];
    bitset<NMAX> viz;
    stack<int> noduriSortTop;
    void dfsSortTop(const int &nod);
public:
    graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
    void adaugaInListaAd(const int &nod1, const int &nod2);
    void sortareTopologica();
};

void graf::adaugaInListaAd(const int &nod1, const int &nod2) {
    listaAd[nod1].push_back(nod2);
}

void graf::dfsSortTop(const int &nod) {
    viz[nod] = true;
    for(int i = 0; i < listaAd[nod].size(); i++){
        if(!viz[listaAd[nod][i]]){
            dfsSortTop(listaAd[nod][i]);
        }
    }
    noduriSortTop.push(nod);
}

void graf::sortareTopologica() {
    for(int i = 1; i <= nrNoduri; i++){
        if (!viz[i]) {
            dfsSortTop(i);
        }
    }
    while(!noduriSortTop.empty()){
        fout<<noduriSortTop.top()<< " ";
        noduriSortTop.pop();
    }
}

int main() {
    int n, m;
    fin >> n  >> m;
    graf G(n, m);
    for(int i = 0; i < m; i ++){
        int n1, n2;
        fin >> n1 >> n2;
        G.adaugaInListaAd(n1, n2);
    }
    G.sortareTopologica();

    return 0;
}