Cod sursa(job #3348315)

Utilizator TeodoRazvanStancu Teodor-Razvan TeodoRazvan Data 20 martie 2026 18:42:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,cnt;
vector<int> tim,ti;
vector<bool> viz,art;
vector<vector<int>>a,sol;
stack<int>s;

void dfs(int nod,int rad){
    ti[nod]=ti[rad]+1;
    tim[nod]=ti[nod];
    viz[nod]=1;
    s.push(nod);
    int fii=0;
    for(auto f:a[nod]){
        if(f==rad) continue;
        if(viz[f]) tim[nod]=min(tim[nod],ti[f]);
        else{
            dfs(f,nod);
            fii++;
            tim[nod]=min(tim[nod],tim[f]);
            if(rad &&ti[nod]<=tim[f])art[nod]=true;
            if(ti[nod]<=tim[f]){
                cnt++;
                while(s.top()!=f){
                    sol[cnt].push_back(s.top());
                    s.pop();
                }
                sol[cnt].push_back(f);
                s.pop();
                sol[cnt].push_back(nod);
            }
            if(!rad&&fii>=2) art[nod]=true;
        }
    }
}

int main(){
    fin>>n>>m;
    a.resize(n+1);
    sol.resize(n+1);
    viz.resize(n+1);
    tim.resize(n+1);
    ti.resize(n+1);
    art.resize(n+1);
    int x,y;
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    fout<<cnt;
    for(auto x:sol){
        sort(x.begin(),x.end());
        for(auto y:x) fout<<y<<" ";
        fout<<'\n';
    }
    return 0;
}