Cod sursa(job #3349256)

Utilizator DasapSapunaru Daniel Dasap Data 26 martie 2026 21:42:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 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;
vector<int>v[NMAX];
vector<vector<int>>biconex;
stack<int>stv;
int n,m,rnk[NMAX],rnkmn[NMAX];
void add(int nod,int tata){
    vector<int>comp{tata};
    int val;
    do{
        val=stv.top();
        stv.pop();
        comp.push_back(val);
    }while(val!=nod);
    biconex.push_back(comp);
}
void dfs(int nod,int tata){
    rnk[nod]=rnkmn[nod]=rnk[tata]+1;
    stv.push(nod);
    for(auto f:v[nod]){
        if(rnk[f]==0){
            dfs(f,nod);
            rnkmn[nod]=min(rnkmn[nod],rnkmn[f]);
            if(rnkmn[f]>=rnk[nod])add(f,nod);
        }
        else rnkmn[nod]=min(rnkmn[nod],rnk[f]);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    fout<<biconex.size()<<'\n';
    for(auto f:biconex){
        for(auto x:f)fout<<x<<' ';
        fout<<'\n';
    }
    return 0;
}