Cod sursa(job #3337070)

Utilizator leonardthethirdSir Leonard The Third leonardthethird Data 26 ianuarie 2026 21:50:59
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

int n,m,x,y;
vector<vector<int>> adj;
vector<int> visited;

vector<int> nivel;
vector<int> nivel_min;

stack<pair<int,int>> st;

int idxComp = 0;
vector<vector<int>> comp_biconexa;

void bison_biconex(const pair<int,int>& pereche){
    set<int> noduri;
    while(true){
        auto [u,v] = st.top();
        st.pop();

        noduri.insert(u);
        noduri.insert(v);

        if((pereche.first == u && pereche.second == v) || (pereche.first == v && pereche.second == u)){
            break;
        }
    }
    vector<int> componenta(noduri.begin(), noduri.end());
    comp_biconexa.push_back(componenta);


}

void as_hali_salam_dar_nam(int nod){
    visited[nod] = 1;
    nivel_min[nod] = nivel[nod];
    for(auto& neigh: adj[nod]){
        if(visited[neigh] == 0){

            nivel[neigh] = nivel[nod] + 1;
            st.push({nod,neigh});
            as_hali_salam_dar_nam(neigh);

            nivel_min[nod] = min(nivel_min[neigh], nivel_min[nod]);

            if(nivel_min[neigh] >= nivel[nod]){
                bison_biconex({nod,neigh});
            }

        }
        else if(visited[neigh] == 1 && nivel[neigh] < nivel[nod] - 1){
            nivel_min[nod] = min(nivel[neigh], nivel_min[nod]);
        }
    }
}

int main(){
    f >> n >> m;
    adj.resize(n+1, vector<int>());
    visited.resize(n+1, 0);
    nivel.resize(n+1, 0);
    nivel_min.resize(n+1, 0);
    for(int i=1; i<=m; i++){
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    nivel[1] = 1;

    as_hali_salam_dar_nam(1);

    g << comp_biconexa.size() << '\n';
    for(int i=0; i< comp_biconexa.size(); i++){
        for(auto& kylie_jenner: comp_biconexa[i]){
            g << kylie_jenner << " ";
        }
        g << '\n';
    }



    return 0;
}