Cod sursa(job #3307426)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 20 august 2025 17:51:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

const int nmax = 1e5 + 5;

stack <int> st;

vector <int> v[nmax];

vector <vector <int>> bcc;

int n, m, lvl[nmax], lowlink[nmax];

void add_bcc (int x, int nod) //muchie critica
{
    vector <int> v{nod};
    int vf;
    do
    {
        vf = st.top ();
        st.pop ();
        v.push_back (vf);
    }
    while (vf != x);
    bcc.push_back (v);
}

void dfs (int nod, int parent)
{
    st.push (nod);
    lvl[nod] = lvl[parent] + 1;
    lowlink[nod] = lvl[nod];
    for (auto x : v[nod])
    {
        if (x == parent)
            continue;
        if (lvl[x] == 0)
        {
            dfs (x, nod);
            if (lowlink[x] >= lvl[nod]) //nod este nod critic
                add_bcc (x, nod);
            lowlink[nod] = min (lowlink[nod], lowlink[x]);
        }
        else //muchie de intoarcere
            lowlink[nod] = min (lowlink[nod], lvl[x]);
    }
}

signed main ()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }
    dfs (1, 0);
    fout << bcc.size () << '\n';
    for (auto comp : bcc)
    {
        for (auto node : comp)
            fout << node << ' ';
        fout << '\n';
    }
}