Cod sursa(job #3322010)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 12 noiembrie 2025 10:40:45
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream f ("biconex.in");
ofstream g ("biconex.out");

const int NMAX = 100000;
int N, M, nrCB, Niv[NMAX+1], Nma[NMAX+1];
bool viz[NMAX+1];

vector <int> G[NMAX+1], CB[NMAX+1];
stack<int> S;

void citire() {
    f >> N >> M;
    //
    int x, y;
    for (int i=1; i<=M; i++) {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS(int nod, int tata) {
    S.push(nod);
    viz[nod] = 1;
    Niv[nod] = Niv[tata] + 1;
    Nma[nod] = Niv[nod];
    //
    for (const auto &x : G[nod]) {
        if (x == tata) continue;
        //
        if (viz[x]) Nma[nod] = min(Nma[nod], Niv[x]);
        else {
            DFS(x, nod);
            Nma[nod] = min(Nma[nod], Nma[x]);
            //
            if (Nma[x] >= Niv[nod]) {
                nrCB++;
                while(S.top() != nod) {
                    CB[nrCB].push_back(S.top());
                    S.pop();
                }
                CB[nrCB].push_back(nod);
            }
        }
    }
}

void afisare() {
    g << nrCB << '\n';
    for (int i=1; i<=nrCB; i++) {
        for (const auto &x : CB[i])
            g << x << ' ';
        g << '\n';
    }
}

int main(){
    citire();
    DFS(1, 0);
    afisare();
    return 0;
}