Cod sursa(job #3341041)

Utilizator ana_maria_772Toc Ana-Maria ana_maria_772 Data 17 februarie 2026 18:15:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <stack>
#define NRnoduri 100001
using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

int n, m, tata[NRnoduri], nivel[NRnoduri], nma[NRnoduri], nrc;
vector <int> vecini[NRnoduri], componente[NRnoduri];
stack <int> s;

void DFS(int nod) {
    s.push(nod);
    nivel[nod]= nivel[tata[nod]] + 1;
    nma[nod]= nivel[nod];
    for (int i=0; i<vecini[nod].size(); i++)
    {
        int next= vecini[nod][i];
        if (nivel[next] and tata[nod]!=next)
        {
            if (nma[nod]>nivel[next])
                nma[nod]= nivel[next];
        }
        else if (!nivel[next])
        {
            tata[next]= nod;
            DFS(next);
            if (nma[next]<nma[nod])
                nma[nod]= nma[next];
            if (nivel[nod]<=nma[next])
            {
                nrc++;
                while (s.top()!=next)
                    componente[nrc].push_back(s.top()), s.pop();
                componente[nrc].push_back(s.top()), s.pop();
                componente[nrc].push_back(nod);
            }
        }
    }
}

int main() {
    cin>>n>>m;
    while (m--) 
    {
        int i, j;
        cin>>i>>j;
        vecini[i].push_back(j);
        vecini[j].push_back(i);
    }
    DFS(1);
    cout<< nrc <<"\n";
    for (int i=1; i<=nrc; i++, cout<<"\n")
        for (int j= componente[i].size() -1; j>=0; j--)
            cout<< componente[i][j] <<" ";
    return 0;
}