Cod sursa(job #3193627)

Utilizator lucriLuchian Cristian lucri Data 15 ianuarie 2024 09:47:08
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
std::ifstream cin("biconex.in");
std::ofstream cout("biconex.out");
int n,m,x,y,low[100010],v[100010],val,nr,vmax;
std::vector<std::vector<int>>a;
std::vector<std::vector<int>>f;
std::vector<int>ans[100010];
void pleaca(int nod,int t)
{
    v[nod]=low[nod]=++val;
    for(auto x:a[nod])
    {
        if(x==t)
            continue;
        if(v[x])
            low[nod]=std::min(low[nod],v[x]);
        else
        {
            pleaca(x,nod);
            f[nod].push_back(x);
            low[nod]=std::min(low[nod],low[x]);
        }
    }
}
void creaza(int nod)
{
    if(nr>vmax)
        vmax=nr;
    if(nod==1)
    {
        for(auto x:f[nod])
        {
            nr=vmax+1;
            ans[nr].push_back(nod);
            if(low[x]!=v[nod])
            {
                ans[nr].push_back(x);
                ++nr;
                creaza(x);
                --nr;
            }
            else
                creaza(x);
        }
        return;
    }
    ans[nr].push_back(nod);
    for(auto x:f[nod])
    {
        if(low[x]<v[nod])
            creaza(x);
        else if(low[x]==v[nod])
        {
            ++nr;
            ans[nr].push_back(nod);
            creaza(x);
            --nr;
        }
        else
        {
            ++nr;
            ans[nr].push_back(nod);
            ans[nr].push_back(x);
            ++nr;
            creaza(x);
            --nr;
            --nr;
        }
    }
}
int main()
{
    cin>>n>>m;
    a.resize(n+5);
    f.resize(n+5);
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    pleaca(1,-1);
    creaza(1);
    int vad=vmax;
    for(int i=1;i<=vmax;++i)
        if(ans[i].size()==1)
            --vad;
    cout<<vad<<'\n';
    for(int i=1;i<=vmax;++i)
        if(ans[i].size()!=1)
        {
            for(auto x:ans[i])
                cout<<x<<' ';
            cout<<'\n';
        }
    return 0;
}