Cod sursa(job #3345555)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 10 martie 2026 08:37:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define NMAX 100005
using namespace std;
ifstream  fin("biconex.in");
ofstream fout("biconex.out");
int N,M,nrb;
int nivel[NMAX],low[NMAX];
vector<int> graph[NMAX];
stack<pair<int,int>> stiva;
set<int> comp[NMAX];

void citire()
{
    fin>>N>>M;

    int u,v;
    for(int i=1; i<=M; i++)
    {
        fin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

void DFS(int parent, int nod)
{
    nivel[nod]=nivel[parent]+1;
    low[nod]=nivel[nod];

    for(int i=0; i<graph[nod].size(); i++)
    {
        int next_nod=graph[nod][i];

        if(next_nod==parent)
        {
            continue;
        }

        if(nivel[next_nod])
        {
           low[nod]=min(low[nod],nivel[next_nod]);
        }
        else
        {
            stiva.push({nod,next_nod});
            DFS(nod,next_nod);

            low[nod]=min(low[nod],low[next_nod]);

            if(low[next_nod]>=nivel[nod])
            {
                nrb++;

                while(!stiva.empty())
                {
                    comp[nrb].insert(stiva.top().first);
                    comp[nrb].insert(stiva.top().second);

                    if(stiva.top().first==nod && stiva.top().second==next_nod)
                    {
                        stiva.pop();
                        break;
                    }

                    stiva.pop();
                }
            }
        }
    }
}

int main()
{
    citire();

    nrb=0;
    DFS(0,1);

    fout<< nrb << "\n";


    for(int i=1; i<=nrb; i++)
    {
        for(auto j:comp[i])
        {
            fout<< j << " ";
        }
        fout<< "\n";
    }

    return 0;
}