Cod sursa(job #3346487)

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

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