Cod sursa(job #2793630)

Utilizator Maria23Dutu Maria Maria23 Data 3 noiembrie 2021 20:22:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.59 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>> ctc;
    void dfsCompTareConexe(int nod, int &nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s, bitset<NMAX> &inStiva);
public:
    graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
    void adaugaInListaAd(const int &nod1, const int &nod2);
    vector<vector<int>> componenteTareConexe();
};

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

vector<vector<int>> graf :: componenteTareConexe() {
    vector<int> nivel;
    vector<int> nivelMin;
    nivel.resize(NMAX);
    nivelMin.resize(NMAX);
    stack<int> s;
    bitset<NMAX> inStiva;
    int niv = 1;
    for(int i = 1; i <= nrNoduri; i++){
        if(!viz[i])
            dfsCompTareConexe(i,  niv, nivel, nivelMin, s, inStiva);
    }
    return ctc;
}

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

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

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.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.componenteTareConexe();
    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;
}