Cod sursa(job #2793089)

Utilizator Maria23Dutu Maria Maria23 Data 2 noiembrie 2021 20:44:39
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <bitset>

using namespace std;
const int NMAX = 100001;

class graf{
private:
    int nrNoduri, nrMuchii;
    vector<int> listaAd[NMAX];
    bitset<NMAX> viz;
    vector<vector<int>> compBiconexe;
    void dfsCompBiconexe(int nod, int nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s);
public:
    graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
    void adaugaInListaAd(const int &nod1, const int &nod2);
    vector<vector<int>> componenteBiconexe();
};

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

vector<vector<int>> graf :: componenteBiconexe() {
    vector<int> nivel;
    vector<int> nivelMin;
    nivel.resize(NMAX);
    nivelMin.resize(NMAX);
    stack<int> s;
    dfsCompBiconexe(1,  1, nivel, nivelMin, s);
    return compBiconexe;
}

void graf::dfsCompBiconexe(int nod, int nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s) {
    viz[nod] = true;
    s.push(nod);
    nivel[nod] = nivelCrt;
    nivelMin[nod] = nivelCrt;

    for(int i = 0; i < listaAd[nod].size(); i++){
        int vecin = listaAd[nod][i];
        if(!viz[vecin]){
            dfsCompBiconexe(vecin, nivelCrt + 1, nivel, nivelMin, s);
            nivelMin[nod] = min(nivelMin[nod], nivelMin[vecin]);
            if(nivelMin[vecin] >= nivel[nod]){
                vector<int> compCrt;
                int nodCompCrt;
                do{
                    nodCompCrt = s.top();
                    compCrt.push_back(nodCompCrt);
                    s.pop();
                }while(nodCompCrt != vecin);
                compCrt.push_back(nod);
                compBiconexe.push_back(compCrt);
            }
        }
        else{
            nivelMin[nod] = min(nivelMin[nod], nivel[vecin]);
        }
    }
}

int main() {
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    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);
    }
    vector<vector<int>> componente = G.componenteBiconexe();
    fout<<componente.size()<<"\n";
    for(int i = 0; i < componente.size(); i++) {
        for(int j = 0; j < componente[i].size(); j++) {
            fout<<componente[i][j]<<"  ";
        }
        fout<<"\n";
    }
    return 0;
}