Cod sursa(job #3373928)

Utilizator Paul13Frincu Paul-Octavian Paul13 Data 8 noiembrie 2026 11:17:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.92 kb
// bibliotecile necesare
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

// fisierele din care scriu si citesc
ifstream fin("biconex.in");
ofstream fout("biconex.out");

// lista de adicenta a grafului la care adaug si id-ul muchie catre vecin
vector<pair<int, int>> graf[100001];

int disc[100001] = {}; // in disc[nod] retin momentul descoperirii nodului
int low[100001] = {}; // low[nod] retine cea mai mic timp descoperit accesibil din subaroborele dfs al nodului
int timp = 0; // contor pentru momentul descoperirii

stack<pair<int,int>> stiva; // ma folosesc de o stiva pentru a memora muchiile intalnite in dfs (nod, vecin)
vector<vector<int>> solutie; // in solutie retin componentele biconexe identificate

// implementez o functie dfs cu 2 argumente ( nodul curent si id-ul muchie parinte)
void dfs(int nod, int muchieParinte){
    disc[nod] = low[nod] = ++timp; // initializez disc[nod] si low[nod] cu timp( momentul descoperirii )

    // parcurg vecinii nodului
    for(auto p : graf[nod]){
        int vecin = p.first;
        int id = p.second;

        if(id == muchieParinte){ // ignor muchia prin care ajungem in nodul curent
            continue;
        }

        // daca nu am mai intalnit nodul
        if(disc[vecin] == 0){
            stiva.push({nod, vecin}); // adaug in stiva perechea {nod, vecin} ce reprezinta muchia dintre cele 2 noduri

            dfs(vecin, id); // aplic dfs pentru vecin

            low[nod] = min(low[nod], low[vecin]); // dupa ce ies din dfs, actualizez low[nod]

            if(low[vecin] >= disc[nod]){ // subarborele lui vecin nu poate ajunge la un stramos al lui nod printr- o muchie de intoarcere
                vector<int> componenta; // memorez nodurile componentei biconexe curente

                // putem forma acum o componenta biconexa
                while(!stiva.empty()){ // cat timp nu am stiva goala
                    int a = stiva.top().first; // citesc nodul
                    int b = stiva.top().second; // si vecinul sau
                    stiva.pop(); // si elimin perechea

                    // le adaug acum in componenta curenta
                    componenta.push_back(a); 
                    componenta.push_back(b);

                    if(a == nod && b == vecin){ // pana cand ajung la muchia de la care a inceput ramura
                        break;
                    }
                }

                // pentru ca in momentul in care scoatem muchiile, adaugam abele capete in vector
                // trebuie sa pastrez fiecare nod o singura data
                sort(componenta.begin(), componenta.end()); // le ordonez crescator

                componenta.erase( // elimin duplicatele
                    unique(componenta.begin(), componenta.end()),
                    componenta.end()
                );

                solutie.push_back(componenta); // adaug coponenta in solutie
            }
        }
        else if (disc[vecin] < disc[nod]){ // am gasit o muchie de intoarcere catre un stramos din arborele dfs
            stiva.push({nod, vecin}); // adaug si muchia (nod, vecin)

            low[nod] = min(low[nod], disc[vecin]); // actualizam low[nod]
        }
    }
}

int main(){
    // introduc numarul de noduri si muchii
    int n, m;
    fin >> n >> m;

    // formez lista de adiacenta
    for(int i = 1; i <= m ; i++){
        int a, b;
        fin >> a >> b;

        graf[a].push_back({b, i});
        graf[b].push_back({a,i});
    }

    // rulez pentru fiecare nod nevizitat dfs-ul
    for(int i = 1; i <= n; i++){
        if(disc[i] == 0){
            dfs(i, -1);
        }
    }

    // afisez solutiile
    fout << solutie.size() << '\n';

    for(auto componenta : solutie){
        for(int nod : componenta){
            fout << nod << " ";
        }
        fout << '\n';
    }

    return 0;
}