Cod sursa(job #3355042)

Utilizator mariusharabariMarius Harabari mariusharabari Data 21 mai 2026 17:21:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=1e5+1;
int n, m, nr, nivel[NMAX], nma[NMAX];
bitset <NMAX> viz;
vector <int> g[NMAX], cb[NMAX];
stack <int> st;

void dfs(int nod, int p){
    viz[nod]=1;
    nivel[nod]=nivel[p]+1;
    nma[nod]=nivel[nod];
    int cil=0;

    st.push(nod);
    //cout<<nod<<'\n';

    for(int vec : g[nod]){
        if(vec==p)
            continue;

        //cout<<"vec "<<vec<<'\n';
        if(viz[vec])
            nma[nod]=min(nma[nod], nivel[vec]);

        else{
            dfs(vec, nod);
            nma[nod]=min(nma[nod], nma[vec]);

            if(nma[vec]>=nivel[nod]){
                //cout<<"cb "<<nr+1<<' '<<nod<<' '<<vec<<'\n';
                nr++;
                while(st.top()!=vec){
                    cb[nr].push_back(st.top());
                    st.pop();
                }
                cb[nr].push_back(st.top());
                st.pop();

                cb[nr].push_back(nod);
            }
        }
    }
}

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

    dfs(1, 0);

    fout<<nr<<'\n';

    for(int i=1;i<=nr;i++){
        for(int a:cb[i])
            fout<<a<<' ';
        fout<<'\n';
    }
    return 0;
}