Cod sursa(job #3336643)

Utilizator Bogdan222Bogdan Caraeane Bogdan222 Data 25 ianuarie 2026 10:11:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 1e5 + 5;
const char nl = '\n';
vector<int> g[NMAX], componente[NMAX];
stack<int> st;
int conexe = 0, nivel_min[NMAX], nivel[NMAX], visitat[NMAX];

void dfs(int nod, int tata, int level) {
    visitat[nod] = 1;
    nivel[nod] = nivel_min[nod] = level;
    st.push(nod);

    for (auto neigh : g[nod]) {
        if (neigh == tata) continue;

        if (visitat[neigh]) {
            // CORECTURĂ 1: Actualizăm corect nivel_min[nod] folosind nivelul vecinului
            nivel_min[nod] = min(nivel_min[nod], nivel[neigh]);
        }
        else {
            dfs(neigh, nod, level + 1);
            nivel_min[nod] = min(nivel_min[nod], nivel_min[neigh]);

            // CORECTURĂ 2: Condiția pentru componente biconexe este >= (punct critic)
            if (nivel_min[neigh] >= nivel[nod]) {
                // Scoatem nodurile până la 'neigh' inclusiv
                int curr_nod;
                do {
                    curr_nod = st.top();
                    st.pop();
                    componente[conexe].push_back(curr_nod);
                } while (curr_nod != neigh);
                
                // CORECTURĂ 3: Nodul 'nod' (părintele) trebuie adăugat și el în componentă,
                // dar NU scos din stivă, pentru că poate face parte din alte componente!
                componente[conexe].push_back(nod);
                conexe++;
            }
        }
    }
}

int main() {
    int n, m, x, y;
    if (!(fin >> n >> m)) return 0;
    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!visitat[i]) {
            dfs(i, 0, 1);
        }
    }
    
    fout << conexe << nl;
    for (int i = 0; i < conexe; i++) {
        for (auto nod_comp : componente[i]) {
            fout << nod_comp << " ";
        }
        fout << nl;
    }
    
    return 0;
}