Cod sursa(job #3272135)

Utilizator AndreeaHzmAndreea Huzum AndreeaHzm Data 28 ianuarie 2025 15:51:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.42 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

#define maxi 100001

using namespace std;

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

stack<pair<int, int>> stivaComponenteBiconexe; // Stiva pentru muchii din componenta biconexa
vector<set<int>> componenteBiconexe;         // Vector de componente biconexe

class Graf {
    int nrNoduri, nrMuchii;         // Numarul de noduri si muchii din graf
    int x, y;                      // Nodurile unei muchii (x, y)
    int vizitat[maxi] = {0};       // Vector pentru a marca nodurile vizitate
    int niv_min[maxi] = {0};       // Nivelul minim pentru fiecare nod
    vector<int> *adiacenta;        // Lista de adiacenta pentru graful neorientat

public:
    Graf();
    ~Graf();

    void citireDFS();               // Citirea grafului neorientat
    void biconex(int nodPlecare, int precedent, int k); // Determinarea componentelor biconexe
    void afisareComponenteBiconexe(); // Afisarea componentelor biconexe
};

Graf::Graf() {
    nrNoduri = nrMuchii = x = y = 0;
    adiacenta = new vector<int>[maxi]; // Alocare memorie pentru lista de adiacenta
}

Graf::~Graf() {
    delete[] adiacenta; // Eliberare memorie pentru lista de adiacenta
}

// Citirea grafului neorientat
void Graf::citireDFS() {
    fin >> nrNoduri >> nrMuchii; // Citim numarul de noduri si muchii
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> x >> y;               // Citim fiecare muchie (x, y)
        adiacenta[x].push_back(y);   // Adaugam nodul y ca vecin al lui x
        adiacenta[y].push_back(x);   // Adaugam nodul x ca vecin al lui y (graful este neorientat)
    }
}

// Determinarea componentelor biconexe folosind DFS
void Graf::biconex(int nodPlecare, int precedent, int k) {
    vizitat[nodPlecare] = k;       // Marcam nivelul curent al nodului
    niv_min[nodPlecare] = k;       // Initializam nivelul minim cu nivelul curent

    for (auto vecin : adiacenta[nodPlecare]) { // Parcurgem toti vecinii nodului curent
        if (vecin != precedent) { // Ignoram muchia care ne-a adus la acest nod (precedent)
            if (!vizitat[vecin]) { // Daca vecinul nu a fost vizitat
                stivaComponenteBiconexe.push({nodPlecare, vecin}); // Adaugam muchia in stiva
                biconex(vecin, nodPlecare, k + 1); // Apel recursiv pentru vecinul curent

                // Actualizam nivelul minim pentru nodul curent
                niv_min[nodPlecare] = min(niv_min[nodPlecare], niv_min[vecin]);

                // Daca vecinul nu este parte dintr-un ciclu
                if (niv_min[vecin] >= vizitat[nodPlecare]) {
                    set<int> componenta; // Initializam componenta biconexa curenta
                    int aux1, aux2;
                    do {
                        aux1 = stivaComponenteBiconexe.top().first;
                        aux2 = stivaComponenteBiconexe.top().second;
                        componenta.insert(aux1); // Adaugam nodurile in componenta
                        componenta.insert(aux2);
                        stivaComponenteBiconexe.pop();
                    } while (aux1 != nodPlecare || aux2 != vecin); // Repetam pana terminam componenta
                    componenteBiconexe.push_back(componenta); // Adaugam componenta la lista finala
                }
            } else if (vizitat[vecin] < vizitat[nodPlecare]) { // Daca exista o muchie de intoarcere
                stivaComponenteBiconexe.push({nodPlecare, vecin}); // Adaugam muchia in stiva
                niv_min[nodPlecare] = min(niv_min[nodPlecare], vizitat[vecin]); // Actualizam nivelul minim
            }
        }
    }
}

// Afisarea componentelor biconexe
void Graf::afisareComponenteBiconexe() {
    fout << componenteBiconexe.size() << "\n"; // Afisam numarul de componente biconexe
    for (auto &componenta : componenteBiconexe) { // Pentru fiecare componenta biconexa
        for (auto nod : componenta) {
            fout << nod << " "; // Afisam toate nodurile componentei
        }
        fout << "\n";
    }
}

int main() {
    Graf g1; // Cream un obiect al clasei Graf
    g1.citireDFS(); // Citim graful neorientat
    g1.biconex(1, 0, 1); // Determinam componentele biconexe pornind de la nodul 1
    g1.afisareComponenteBiconexe(); // Afisam componentele biconexe

    fin.close(); // Inchidem fisierul de intrare
    fout.close(); // Inchidem fisierul de iesire

    return 0;
}