Cod sursa(job #3345053)

Utilizator DasapSapunaru Daniel Dasap Data 7 martie 2026 19:00:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=1e5;
int n,m,x,y,k;
stack<int>s;
vector<int>v[NMAX+5];
vector<vector<int>>compbiconexe;
int nvl[NMAX+5],nvlmin[NMAX+5];
void addcmp(int nod,int tata){
    vector<int>comp={tata};
    k=0;
    do{
        k=s.top();
        comp.push_back(k);
        s.pop();
    }while(k!=nod);
    compbiconexe.push_back(comp);
}
void dfs(int nod,int tata){
    s.push(nod);
    nvl[nod]=nvl[tata]+1;
    nvlmin[nod]=nvl[nod];
    for(auto f:v[nod]){
        if(f==tata)continue;
        if(nvl[f]==0){
            dfs(f,nod);
            if(nvlmin[f]>=nvl[nod])addcmp(f,nod);
            nvlmin[nod]=min(nvlmin[nod],nvlmin[f]);
        }
        else{
            nvlmin[nod]=min(nvlmin[nod],nvl[f]);
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    fout<<compbiconexe.size()<<'\n';
    for(auto x:compbiconexe){
        for(auto y:x)fout<<y<<' ';
        fout<<'\n';
    }
    return 0;
}