Cod sursa(job #3303835)

Utilizator unomMirel Costel unom Data 18 iulie 2025 11:59:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m;
vector<int> v[100005];
int viz[100005];
int niv[100005];
int nma[100005];
stack<int> s;
vector<vector<int>> ans;

void dfs(int nod, int tata)
{
    viz[nod] = 1;
    niv[nod] = niv[tata] + 1;
    nma[nod] = niv[nod];

    s.push(nod);

    for(auto it: v[nod])
    {
        if(it == tata)
        {
            continue;
        }

        if(viz[it] == 1)
        {
            nma[nod] = min(nma[nod], niv[it]);
        }
        else
        {
            dfs(it, nod);

            nma[nod] = min(nma[nod], nma[it]);

            if(niv[nod] <= nma[it])
            {
                vector<int> comp;

                while(s.top() != it)
                {
                    comp.push_back(s.top());
                    s.pop();
                }

                comp.push_back(it);
                s.pop();

                comp.push_back(nod);

                ans.push_back(comp);
            }
        }
    }
}

int main()
{
    in>>n>>m;

    int x, y;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);

    out<<ans.size()<<'\n';
    for(auto vec: ans)
    {
        for(auto it: vec)
        {
            out<<it<<" ";
        }
        out<<'\n';
    }

    return 0;
}