Cod sursa(job #3374834)

Utilizator carlosavbossAvramescu Carlos-Cristian carlosavboss Data 9 noiembrie 2026 14:50:59
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX = 100005;
const int MMAX = 200005;

int n, m;

// Liste de adiacenta cu vectori statici.
int lst[NMAX], vecin[2 * MMAX], urm[2 * MMAX], nrm;

int disc[NMAX];        // momentul descoperirii in DFS (0 = nevizitat)
int low[NMAX];         // cel mai mic disc accesibil din subarborele lui u printr-o muchie de intoarcere
int timp;
int stiva[NMAX], vf;   // nodurile vizitate care nu au fost inca puse intr-o componenta

// Componentele, memorate una dupa alta intr-un singur vector:
// componenta c ocupa pozitiile inceput[c] .. inceput[c+1]-1 din noduri[].
int noduri[2 * NMAX], inceput[NMAX], nrc, total;

void adauga(int u, int v) {
    nrm++;
    vecin[nrm] = v;
    urm[nrm] = lst[u];
    lst[u] = nrm;
}

void dfs(int u, int parinte) {
    disc[u] = low[u] = ++timp;
    stiva[++vf] = u;

    for (int k = lst[u]; k != 0; k = urm[k]) {
        int v = vecin[k];
        if (disc[v] == 0) {
            dfs(v, u);
            if (low[v] < low[u]) low[u] = low[v];

            // Din subarborele lui v nu se poate urca deasupra lui u => u e punct de articulatie
            // (sau radacina) care separa subarborele lui v. Nodurile din stiva pana la v,
            // impreuna cu u, formeaza o componenta biconexa.
            if (low[v] >= disc[u]) {
                nrc++;
                inceput[nrc] = total + 1;
                int w;
                do {
                    w = stiva[vf--];
                    noduri[++total] = w;
                } while (w != v);
                noduri[++total] = u;   // u ramane in stiva, poate face parte si din alte componente
            }
        } else if (v != parinte && disc[v] < low[u]) {
            low[u] = disc[v];          // muchie de intoarcere catre un stramos
        }
    }
}

int main() {
    fin >> n >> m;
    for (int e = 1; e <= m; e++) {
        int x, y;
        fin >> x >> y;
        adauga(x, y);
        adauga(y, x);
    }

    for (int i = 1; i <= n; i++)
        if (disc[i] == 0) {
            vf = 0;
            dfs(i, 0);
        }
    inceput[nrc + 1] = total + 1;

    fout << nrc << "\n";
    for (int c = 1; c <= nrc; c++) {
        for (int p = inceput[c]; p < inceput[c + 1]; p++)
            fout << noduri[p] << " ";
        fout << "\n";
    }
    return 0;
}