Cod sursa(job #2817711)

Utilizator RoberttoPopescu Paullo Robertto Karloss Robertto Data 14 decembrie 2021 01:33:01
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.94 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

struct muchie2 {
    int destinatie, cost, capacitate;
    muchie2 (int destinatie, int cost, int capacitate) : destinatie(destinatie), cost(cost), capacitate(capacitate) {}
};

struct muchie {
    int destinatie;
    muchie (int destinatie) : destinatie(destinatie) {}
};

class Graf {
    int nrNoduri, nrMuchii;
    bool eOrientat, arePonderi;
    //vector<int> *adiacenta; // lista de vecini
    vector<vector<muchie>> adiacenta;
public:
    Graf(int nrNoduri, int nrMuchii, const bool eOrientat, const bool arePonderi);
    void citire();
    void rezolvaBiconex();
private:
    void biconex(int nodPlecare, int precedent, int k, stack<pair<int, int>> &stivaComponenteBiconexe,
                   vector<set<int>> &componenteBiconexe, vector<int> &vizitat, vector<int> &niv_min);
};

void Graf::biconex(int nodPlecare, int precedent, int k, stack<pair<int, int>> &stivaComponenteBiconexe,
                   vector<set<int>> &componenteBiconexe, vector<int> &vizitat, vector<int> &niv_min) {
    vizitat[nodPlecare] = k;
    niv_min[nodPlecare] = k;
    for (auto &i: adiacenta[nodPlecare]) {
        int vecin = i.destinatie;
        if (vecin != precedent) { // pentru optimizare (iese din timp altfel, uneori),
            // daca vecinul curent nu s-a executat la pasul anterior
            if (!vizitat[vecin]) { // daca vecinul nu a fost vizitat
                stivaComponenteBiconexe.push(make_pair(nodPlecare, vecin));
                biconex(vecin, nodPlecare, k + 1, stivaComponenteBiconexe, componenteBiconexe, vizitat,
                        niv_min); // reapelez DF din nodul in care am ajuns
                if (niv_min[nodPlecare] > niv_min[vecin]) // daca face parte din ciclu
                    niv_min[nodPlecare] = niv_min[vecin]; // actualizez nivelul minim
                if (niv_min[vecin] >= vizitat[nodPlecare]) {
                    // daca un vecin are nivelul minim mai mare sau egal decat nivelul tatalui sau
                    // (vizitat este pe pos de nivel din muchia critica, i.e. nivelul din arborele DF),
                    // inseamna ca nu face parte dintr-un ciclu, deci am gasit o componenta biconexa
                    set<int> aux;
                    int aux1, aux2;
                    do {
                        aux1 = stivaComponenteBiconexe.top().first;
                        aux2 = stivaComponenteBiconexe.top().second;
                        aux.insert(aux1);
                        aux.insert(aux2);
                        stivaComponenteBiconexe.pop();
                    } while (aux1 != nodPlecare || aux2 != vecin);
                    componenteBiconexe.push_back(aux);
                }
            } else if (niv_min[nodPlecare] > vizitat[vecin]) { // daca nodul curent a fost deja vizitat
                // si daca exista o muchie de intoarcere de la nodPlecare la nodul curent, exista legatura cu un stramos
                // (muchie de intoarcere de la nodPlecare la nodul curent)
                niv_min[nodPlecare] = vizitat[vecin]; // nivelul nodului de Plecare
                // va fi nivelul stramosului sau (nodul deja vizitat)
            }
        }
    }
}

void Graf::rezolvaBiconex() {
    stack<pair<int, int>> stivaComponenteBiconexe;
    vector<set<int>> componenteBiconexe;

    vector<int> vizitat(nrNoduri + 1, 0);
    vector<int> niv_min(nrNoduri + 1, 0);

    biconex(1, 0, 1, stivaComponenteBiconexe, componenteBiconexe, vizitat, niv_min);
    set<int>::iterator it;
    fout << componenteBiconexe.size() << "\n";
    for (auto &i: componenteBiconexe) {
        for (it = i.begin(); it != i.end(); it++) {
            fout << *it << " ";
        }
        fout << "\n";
    }
}


int main() {
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri, nrMuchii, false, false);
    g1.citire();
    g1.rezolvaBiconex();

    fin.close();
    fout.close();
    return 0;
}

void Graf::citire() {
    int sursa, destinatie, cost, capacitate; // extremitate muchie stanga respectiv dreapta
    //adiacenta = new vector<int>[nrNoduri + 1];
    adiacenta.resize(nrNoduri+1);
    if (!arePonderi) {
        if (eOrientat)
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie;
                adiacenta[sursa].push_back(muchie(destinatie));
            }
        else
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie;
                adiacenta[sursa].push_back(muchie(destinatie));
                adiacenta[destinatie].push_back(muchie(sursa));
            }
    }
}

Graf::Graf(int nrNoduri, int nrMuchii, const bool eOrientat, const bool arePonderi) {
    this->nrNoduri=nrNoduri;
    this->nrMuchii=nrMuchii;
    this->eOrientat=eOrientat;
    this->arePonderi=arePonderi;
}