Cod sursa(job #3305556)

Utilizator davidgrusGeorge David Rusanescu davidgrus Data 2 august 2025 17:54:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#pragma GCC optimize("O3,unroll-loops,fast-math")
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int dm=1e5+55;
int n,m,lw[dm],nv[dm],x,y,st[dm],vf,nrc;
vector<int>sol[dm],a[dm];
bitset<dm>vz;
void dfs(int x,int tat)
{
    st[++vf]=x;
    nv[x]=nv[tat]+1;
    lw[x]=nv[x];
    vz[x]=1;
    for(auto y:a[x])
    {
        if(vz[y])
            lw[x]=min(lw[x],nv[y]);
        else
        {
            dfs(y,x);
            lw[x]=min(lw[x],lw[y]);
            if(nv[x]<=lw[y])
            {
               // isart[x]=1; //this and root
                ++nrc;
                while(st[vf]!=y)
                {
                    sol[nrc].pb(st[vf]);
                    vf--;
                }
                vf--;
                sol[nrc].pb(y),sol[nrc].pb(x);
            }
        }
    }
}
int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    dfs(1,0);
    fout<<nrc<<'\n';
    for(int i=1;i<=nrc;++i,fout<<'\n')
        for(auto w:sol[i])
        fout<<w<<" ";
}