Cod sursa(job #3349180)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 25 martie 2026 21:00:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[100009], bcc[100009];
int curr=0;
int niv[100009], vf=0, st[100009], low[100009];
void dfs (int nod, int tata)
{
    low[nod]=niv[nod];
    st[++vf]=nod;
    int x=nod;
    for (auto y:v[nod])
    {
        if (y!=tata)
        {
            if (niv[y])
                low[x]=min (low[x], niv[y]);
            else
            {
                niv[y]=niv[x]+1;
                dfs (y, x);
                low[x]=min (low[x], low[y]);
                if (low[y]>=niv[x])
                {
                    curr++;
                    while (st[vf]!=y)
                    {
                        bcc[curr].push_back(st[vf]);
                        vf--;
                    }
                    bcc[curr].push_back(y);
                    vf--;
                    bcc[curr].push_back(x);

                }
            }
        }
    }
}
signed main ()
{
    int n, m;
    f >> n >> m;
    while (m--)
    {
        int x, y;
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    niv[1]=1;
    dfs (1, 0);
    g << curr << '\n';
    for (int i=1; i<=curr; i++)
    {
        for (auto x:bcc[i])
            g << x << ' ';
        g <<'\n';
    }

}