Cod sursa(job #2796927)

Utilizator thatnickkNicu-Victor Ardeleanu thatnickk Data 9 noiembrie 2021 00:30:12
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 8.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

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

class Graf{
    private:
        bool orientat;
        int nrNoduri;
        int nrMuchii;
        vector<vector<int>> listaAdiacenta;
        vector<int> topologie;

        void bfs(vector<int>& distante, vector<bool>& vizitat, int nodStart){
            queue<int> coada;
            coada.push(nodStart);
            distante[nodStart] = 0;

            while (coada.empty() == false){
                int nodCurent = coada.front();
                vizitat[nodCurent] = true;
                for (auto i : listaAdiacenta[nodCurent]){
                    if (vizitat[i] == false){
                        coada.push(i);
                        distante[i] = distante[nodCurent] + 1;
                        vizitat[i] = true;
                    }
                }
                coada.pop();
            }
        }        

        void dfs(vector<bool>& vizitat, int nodCurent){
            vizitat[nodCurent] = true;
            for (auto i : listaAdiacenta[nodCurent])
                if (vizitat[i] == false)
                    dfs(vizitat, i);
        }

        void dfsbiconex(int nodCurent, int nodAnterior, int adancimeCurenta, vector<vector<int>>& componente, stack<int>& stiva, vector<bool>& vizitat, vector<int>& adancime, vector<int>& adancimeMin){
            adancime[nodCurent] = adancimeCurenta;
            vizitat[nodCurent] = true;
            adancimeMin[nodCurent] = adancimeCurenta;
            stiva.push(nodCurent);

            for (auto i : listaAdiacenta[nodCurent]){
                if (i != nodAnterior){
                    if (vizitat[i] == true){
                        adancimeMin[nodCurent] = min(adancimeMin[nodCurent], adancime[i]);
                    }
                    else{
                        dfsbiconex(i, nodCurent, adancimeCurenta + 1, componente, stiva, vizitat, adancime, adancimeMin);
                        adancimeMin[nodCurent] = min(adancimeMin[nodCurent], adancimeMin[i]);
                        if(adancime[nodCurent] <= adancimeMin[i]){
                            vector<int> componenta;
                            componenta.push_back(nodCurent);
                            int nod = stiva.top();
                            stiva.pop();
                            componenta.push_back(nod);
                            while (i != nod){
                                nod = stiva.top();
                                stiva.pop();
                                componenta.push_back(nod);
                            }

                            componente.push_back(componenta);
                        }
                    }
                }
            }
            }

        void TarjanDFS(int nodCurent, vector<vector<int>>& componente, vector<int>& ordineDescoperit, vector<int>& adancimeMinima, stack<int>& stiva, vector<bool>& peStiva, int& timp){
            ordineDescoperit[nodCurent] = timp;
            adancimeMinima[nodCurent] = timp;
            peStiva[nodCurent] = true;
            stiva.push(nodCurent);
            
            timp++;

            for (auto i : listaAdiacenta[nodCurent]){
                if (ordineDescoperit[i] == -1){
                    TarjanDFS(i, componente, ordineDescoperit, adancimeMinima, stiva, peStiva, timp);
                    adancimeMinima[nodCurent] = min(adancimeMinima[nodCurent],adancimeMinima[i]); 
                }
                else if (peStiva[i] == true)
                    adancimeMinima[nodCurent] = min(adancimeMinima[nodCurent], ordineDescoperit[i]);
            }

            if (adancimeMinima[nodCurent] == ordineDescoperit[nodCurent]){
                vector<int> componenta;

                int nod = stiva.top();
                stiva.pop();
                peStiva[nod] = false;
                componenta.push_back(nod);
                while (nod != nodCurent){
                    nod = stiva.top();
                    stiva.pop();
                    peStiva[nod] = false;
                    componenta.push_back(nod); 
                }

                componente.push_back(componenta);
            }
        }

        void sortareTopologica(int nod, vector<bool>& vizitat){
            vizitat[nod] = true;
            for (int i : listaAdiacenta[nod]){
                if (!vizitat[i])
                    sortareTopologica(i, vizitat);
            }
            topologie.push_back(nod);
        } 

    public:
        Graf(){
            nrNoduri = 0;
            nrMuchii = 0;
            orientat = false;
            vector<int> gol;
            for (int i = 0; i < nrNoduri; i++)
                listaAdiacenta.push_back(gol);
        }
        Graf(int nrNod, int nrMuc, bool esteOrientat){
            nrNoduri = nrNod;
            nrMuchii = nrMuc;
            orientat = esteOrientat;            
            vector<int> gol;
            for (int i = 0; i < nrNoduri; i++)
                listaAdiacenta.push_back(gol);
        }

        bool getOrient(){
            return orientat;
        }
        int getNrNoduri(){
            return nrNoduri;
        }
        int getNrMuchii(){
            return nrMuchii;
        }

        void setOrient(bool orient){
            orientat = orient;
        }
        void setNrNoduri(int nr){
            nrNoduri = nr;
        }
        void setNrMuchii(int nr){
            nrMuchii = nr;
        }

        void setareGraf(){
            if (orientat){
                int x, y;
                for(int i = 0; i < nrMuchii; i++){
                    fin >> x >> y;
                    x--;
                    y--;
                    listaAdiacenta[x].push_back(y);
                }
            }
            else{
                int x, y;
                for(int i = 0; i < nrMuchii; i++){
                    fin >> x >> y;
                    x--;
                    y--;
                    listaAdiacenta[x].push_back(y);
                    listaAdiacenta[y].push_back(x);
                }
            }
        }

        vector<int> distanteMinime(int nodStart){
            vector<int> distante(nrNoduri, -1);
            vector<bool> vizitat(nrNoduri, false);

            bfs(distante, vizitat, nodStart);
            return distante;
        }

        int nrCompConexe(){
            int nr = 0;
            vector<bool> vizitat(nrNoduri, false);
            for (int i = 0; i < nrNoduri; i++)
                if (vizitat[i] == false){
                    dfs(vizitat, i);
                    nr++;
                }
            
            return nr;
        }

        vector<vector<int>> ComponenteBiconexe(){
            vector<bool> vizitat(nrNoduri, false);
            vector<int> adancime(nrNoduri, -1);
            vector<int> adancimeMin(nrNoduri, -1);
            stack<int> stiva;
            vector<vector<int>> componente;

            dfsbiconex(0, -1, 0, componente, stiva, vizitat, adancime, adancimeMin);

            return componente;
        }

        vector<vector<int>> ComponenteTareConexe(){
            vector<vector<int>> componente;
            stack<int> stiva;
            vector<bool> peStiva(nrNoduri, false);
            vector<int> ordineDescoperire(nrNoduri, -1);
            vector<int> adancimeMinima(nrNoduri, -1);
            int timp = 0;

            for (int i = 0; i < nrNoduri; i++){
                if (ordineDescoperire[i] = -1)
                    TarjanDFS(i, componente, ordineDescoperire, adancimeMinima, stiva, peStiva, timp);
            }
            return componente;
        }

        void topologic(){
            vector<bool> vizitat(nrNoduri, false);
            for (int i = 0; i < nrNoduri; i++){
                if(!vizitat[i])
                    sortareTopologica(i, vizitat);
            }

            for (int i = topologie.size() - 1; i >= 0; i--){
                fout << topologie[i] + 1 << " ";
            }
        }

};

int main(){
    int n, m;
    fin >> n >> m;
    Graf graf(n,m,true);

    graf.setareGraf();

    graf.topologic();
    return 0;
}