Cod sursa(job #3350960)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 15 aprilie 2026 11:26:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX=100005;
vector<int> adj[NMAX];
int n,m;
int x,y;
bool b[NMAX];
int lvl[NMAX],low[NMAX];
stack<int> stec;
vector<vector<int>> fin;
vector<int> ras;
void dfs(int nod,int dad)
{
    low[nod]=nod;
    stec.push(nod);
    for(auto fiu:adj[nod])
    {
        if(fiu==dad)
        {
            continue;
        }
        if(b[fiu]==0)
        {
            b[fiu]=1;
            lvl[fiu]=lvl[nod]+1;
            dfs(fiu,nod);
            if(lvl[low[fiu]]<lvl[low[nod]])
            {
                low[nod]=low[fiu];
            }
            if(lvl[low[fiu]]>=lvl[nod])
            {
                ras.clear();
                while(stec.top()!=fiu)
                {
                    ras.push_back(stec.top());
                    stec.pop();
                }
                ras.push_back(stec.top());
                stec.pop();
                ras.push_back(nod);
                fin.push_back(ras);
            }
        }
        if(b[fiu]==1)
        {
            if(lvl[low[nod]]>lvl[fiu])
            {
                low[nod]=fiu;
            }
        }
    }
    b[nod]=2;
    return;
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    b[1]=1;
    lvl[1]=1;
    dfs(1,0);
    out<<fin.size()<<"\n";
    for(auto vec:fin)
    {
        for(auto nod:vec)
        {
            out<<nod<<" ";
        }
        out<<"\n";
    }
}