Cod sursa(job #2796830)

Utilizator anaop32Oprea Ana-Maria anaop32 Data 8 noiembrie 2021 20:50:46
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

class Graf{
private:
    int nrNoduri;
    vector<vector<int>> listaVecini;
public:
    Graf();
    Graf(int);
    int get_nrNoduri();
    void set_nrNoduri(int);
    void set_listaVecini();
    void adaugaMuchie(int, int);

    // CTC
    void Tarjan();
    void DFS_CTC(int, vector<int>&, vector<int>&, stack<int>&, vector<bool>&, int&);
};

Graf::Graf(int n){
    this->nrNoduri = n;
    for (int i = 1; i <= nrNoduri; i++){
        vector<int> aux;
        listaVecini.push_back(aux);
    }
}

Graf::Graf(){
   
}


void Graf::adaugaMuchie(int m1, int m2){
    listaVecini[m1].push_back(m2);
}

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

void Graf::set_nrNoduri(int n){
    this->nrNoduri = n;
}

void Graf::set_listaVecini(){
    for (int i = 1; i <= this->get_nrNoduri(); i++){
        vector<int> aux;
        listaVecini.push_back(aux);
    }
}

void Graf::DFS_CTC(int nod_curent, vector<int> &descoperit, vector<int> &low, stack<int> &stiva, vector<bool> &membruStiva, int &nr){
    static int timp = 0;
    descoperit[nod_curent] = low[nod_curent] = timp++;
    stiva.push(nod_curent);
    membruStiva[nod_curent] = true;

    for (auto elem: listaVecini[nod_curent]){
        if (descoperit[elem] == -1){
            DFS_CTC(elem, descoperit, low, stiva, membruStiva, nr);
        }
        if(membruStiva[elem] == true){
            low[nod_curent] = min(low[nod_curent], low[elem]);
        }
    }
    if (descoperit[nod_curent] == low[nod_curent]){
        for (int nod = stiva.top();;nod = stiva.top()){
            stiva.pop();
            membruStiva[nod] = false;
            low[nod] = descoperit[nod_curent];
            if (nod == nod_curent)
                break;
        }
        nr++;
    }
}

void Graf::Tarjan(){
    vector<int> descoperit(this->get_nrNoduri(), -1);
    vector<int> low(this->get_nrNoduri(), -1);
    stack<int> stiva;
    vector<bool> membruStiva(this->get_nrNoduri(), false);
    int nr = 0; // numarul componenetelor tare conexe

    for (int i = 0; i < this->get_nrNoduri(); i++){
        if (descoperit[i] == -1)
            DFS_CTC(i, descoperit, low, stiva, membruStiva, nr);
    }
    g << nr << "\n";
    set<int> multime;
    for (int i = 0; i < this->get_nrNoduri(); i++){
        multime.insert(low[i]);
    }
    for (auto elem : multime){
        for (int i = 0; i < this->get_nrNoduri(); i++){
            if (low[i] == elem)
               g << i + 1<< " ";
        }
        g << "\n";
    }
}


int main(){
    Graf g1;
    int n, m, nod1, nod2;
    f >> n >> m;
    g1.set_nrNoduri(n);
    g1.set_listaVecini();

    for (int i = 1; i <= m; i++){
        f >> nod1 >> nod2;
        g1.adaugaMuchie(nod1 - 1, nod2 - 1);
    }
    g1.Tarjan();
    return 0;
}