Cod sursa(job #2797668)

Utilizator ptr22222Petru Popescu ptr22222 Data 10 noiembrie 2021 13:49:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

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

const int nmax = 100001;

class Graf
{
private:
    bool orientat;
    int nrNoduri;
    vector <int> listaAdiacenta[nmax];
public:
    Graf(int nrNoduri = 0, bool orientat = false);
    int get_nrNoduri();
    void citireMuchii(int nrMuchii);
    vector<int> BFS(int start);
    void DFS(int nodCurent, bool *vizitatDFS);
    int nrComponenteConexe();
    void DFSStiva(int nodcurent, bool *vizitatDFS, stack<int> &stivaTimp);
    void sortareTopologica();
    void TarjanCTC(int &timpCurent, int nodCurent, int *timpDescoperire, int *minimLegat, bool *estePeStiva, stack <int> &stiva, vector<vector<int>> &componenteTConexe);
    void CTC();
    void TarjanBC(int &timpCurent, int nodCurent, int parinte, int *timpDescoperire, int *minimLegat, stack <int> &stiva, vector<vector<int>> &componenteBConexe);
    void BC();
};

Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
    this->nrNoduri = nrNoduri;
    this->orientat = orientat;
}

int Graf::get_nrNoduri()
{
    return this->nrNoduri;
}

void Graf::citireMuchii(int nrMuchii)
{
    int nod1, nod2;
    for(int i = 0; i < nrMuchii; i++)
    {
        in >> nod1 >> nod2;
        listaAdiacenta[nod1].push_back(nod2);
        if(!orientat)
        {
            listaAdiacenta[nod2].push_back(nod1);
        }
    }
}

void Graf::TarjanBC(int &timpCurent, int nodCurent, int parinte, int *timpDescoperire, int *minimLegat, stack <int> &stiva, vector<vector<int>> &componenteBConexe)
{
    stiva.push(nodCurent);
    timpDescoperire[nodCurent] = timpCurent;
    minimLegat[nodCurent] = timpCurent;
    timpCurent++;
    for(auto vecin:listaAdiacenta[nodCurent])
    {
        if(vecin != parinte)
        {
            if(timpDescoperire[vecin] == 0)
            {
                TarjanBC(timpCurent, vecin, nodCurent, timpDescoperire, minimLegat, stiva, componenteBConexe);
                minimLegat[nodCurent] = min(minimLegat[nodCurent], minimLegat[vecin]);
                if (timpDescoperire[nodCurent] <= minimLegat[vecin]) {
                    vector<int> componentaCurenta;
                    int aux;
                    componentaCurenta.push_back(nodCurent);
                    do {
                        aux = stiva.top();
                        componentaCurenta.push_back(aux);
                        stiva.pop();
                    } while (aux != vecin);
                    componenteBConexe.push_back(componentaCurenta);
                }
            }
            else
            {
                minimLegat[nodCurent] = min(minimLegat[nodCurent], timpDescoperire[vecin]);
            }
        }
    }
}

void Graf::BC()
{
    int timpCurent = 1;
    int timpDescoperire[nmax] = {0}, minimLegat[nmax] = {0};
    bool estePeStiva[nmax] = {false};
    stack <int> stiva;
    vector <vector <int>> componenteBConexe;
    TarjanBC(timpCurent, 1, -1, timpDescoperire, minimLegat, stiva, componenteBConexe);
    out << componenteBConexe.size() << "\n";
    for(auto x:componenteBConexe)
    {
        for(auto y:x)
        {
            out << y << " ";
        }
        out << "\n";
    }
}

int main() {
    int n, m;
    in >> n >> m;
    Graf g(n,false);
    g.citireMuchii(m);
    g.BC();
    return 0;
}