Cod sursa(job #2796450)

Utilizator thatnickkNicu-Victor Ardeleanu thatnickk Data 8 noiembrie 2021 02:29:05
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

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

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

        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);
                        }
                    }
                }
            }
            }

    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;
        }

};

int main(){
    int n, m;
    vector<vector<int>> componente;
    fin >> n >> m;
    Graf graf(n,m,false);
    graf.setareGraf();
    componente = graf.ComponenteBiconexe();

    fout<<componente.size()<<"\n";

    for (int i = 0; i < componente.size(); i++){
        for (auto nd : componente[i]){
            fout << nd+1 << " ";
        }
        fout<< "\n";
    }  
    return 0;
}