Cod sursa(job #3348007)

Utilizator altomMirel Fanel altom Data 19 martie 2026 10:31:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX=1e5+5;
const int MMAX=2e5+5;
int n, m;
vector<int> ad[NMAX];
vector<vector<int>> sol;
int nivel[NMAX], nma[NMAX];
stack<int> st;

void addCompBiconex(int x, int y){
    vector<int> comp={x};

    while(!st.empty()){
        int vf=st.top();
        comp.push_back(vf);
        st.pop();
        if(vf==y)
            break;
    }

    sol.push_back(comp);
}

void dfs(int nod, int tata){
    st.push(nod);

    nivel[nod]=nivel[tata]+1;
    nma[nod]=nivel[nod];

    for(auto vecin: ad[nod]){
        if(vecin==tata)
            continue;
        if(nivel[vecin]==0){
            dfs(vecin, nod);
            if(nma[vecin]>=nivel[nod]){
                addCompBiconex(nod, vecin);
            }

            nma[nod]=min(nma[nod], nma[vecin]);
        }else{
            nma[nod]=min(nma[nod], nivel[vecin]);
        }
    }
}

int main()
{
    fin>>n>>m;
    int a, b;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        ad[a].push_back(b);
        ad[b].push_back(a);
    }

    dfs(1, 0);

    fout<<sol.size()<<'\n';
    for(auto comp: sol){
        for(auto nod: comp)
            fout<<nod<<" ";
        fout<<'\n';
    }


    return 0;
}