Cod sursa(job #3372199)

Utilizator albertcc26Comarniceanu Albert Nicolae albertcc26 Data 2 noiembrie 2026 18:32:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int>>adj;
vector<vector<int>>componente_biconexe;
vector<int>viz;
vector<int>timp_descoperire;
vector<int>low;
stack<int> st;

int n,m,cnt=1;

void dfs(int nod, int tata){
    viz[nod]=1;
    timp_descoperire[nod]=low[nod]=cnt;
    cnt++;
    st.push(nod);
    
    for(int i: adj[nod])
    {

        if(viz[i]==0)
        {
            dfs(i,nod);

            low[nod]=min(low[nod],low[i]);

            
if(low[i] >= timp_descoperire[nod]) 
{
    vector<int> componenta_curenta;
    int extras;
    
    do {
        extras = st.top();        
        st.pop();                 
        componenta_curenta.push_back(extras);
    } while (extras != i);

    componenta_curenta.push_back(nod);

    componente_biconexe.push_back(componenta_curenta);
}
        }
            else
        if(i != tata)
        {
        low[nod]=min(low[nod],timp_descoperire[i]);
        }
    }           

}

int main(){
    f>>n>>m;

    adj.resize(n + 5);
    viz.resize(n + 5);
    timp_descoperire.resize(n + 5);
    low.resize(n + 5);


    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;

        adj[x].push_back(y);
        adj[y].push_back(x);

    }

    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0){
            dfs(i,0);
        }
    }


    g<<componente_biconexe.size()<<"\n";

    for(int i=0;i<componente_biconexe.size();i++)
    {
        for(int j=0;j<componente_biconexe[i].size();j++)
        {
        g<<componente_biconexe[i][j]<<" ";
        }
        g<<"\n";
    }

return 0;
}