Cod sursa(job #3193628)

Utilizator lucriLuchian Cristian lucri Data 15 ianuarie 2024 09:56:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 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,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,int comp)
{
    if(comp>vmax)
        vmax=comp;
    if(nod==1)
    {
        for(auto x:f[nod])
        {
            ans[vmax+1].push_back(nod);
            if(low[x]!=v[nod])
            {
                ans[vmax+1].push_back(x);
                creaza(x,vmax+2);
            }
            else
                creaza(x,vmax+1);
        }
        return;
    }
    ans[comp].push_back(nod);
    for(auto x:f[nod])
    {
        if(low[x]<v[nod])
            creaza(x,comp);
        else if(low[x]==v[nod])
        {
            ans[vmax+1].push_back(nod);
            creaza(x,vmax+1);
        }
        else
        {
            ans[vmax+1].push_back(nod);
            ans[vmax+1].push_back(x);
            creaza(x,vmax+2);
        }
    }
}
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,0);
    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;
}