Cod sursa(job #3374300)

Utilizator ArcopieBirghilescu Alexandru Arcopie Data 8 noiembrie 2026 22:18:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int N_MAX = 100005;

vector<int> g[N_MAX];
int niv[N_MAX];
int niv_min[N_MAX];
vector<int> stiva;
vector<vector<int>> cb;
int timp;

void dfs(int nod, int tata) {
    timp++;
    niv[nod] = timp;
    niv_min[nod] = timp;
    stiva.push_back(nod);

    for (int vecin : g[nod]) {
        if (vecin == tata) {
            continue;
        }

        if (niv[vecin] == 0) {
            // explorare in adancime
            dfs(vecin, nod);
            niv_min[nod] = min(niv_min[nod], niv_min[vecin]);

            // extragere componenta biconexa daca vecinul nu urca mai sus de nodul curent
            if (niv_min[vecin] >= niv[nod]) {
                vector<int> comp;
                int extras;
                do {
                    extras = stiva.back();
                    stiva.pop_back();
                    comp.push_back(extras);
                } while (extras != vecin);

                // adaugam si punctul de articulatie in componenta
                comp.push_back(nod);
                cb.push_back(comp);
            }
        } else {
            // actualizare nivel minim folosind muchia de intoarcere
            niv_min[nod] = min(niv_min[nod], niv[vecin]);
        }
    }
}

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

    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // apelam dfs pentru fiecare componenta conexa a grafului
    for (int i = 1; i <= n; ++i) {
        if (niv[i] == 0) {
            dfs(i, 0);
        }
    }

    fout << cb.size() << "\n";
    for (int i = 0; i < cb.size(); ++i) {
        for (int j = 0; j < cb[i].size(); ++j) {
            fout << cb[i][j] << " ";
        }
        fout << "\n";
    }

    fin.close();
    fout.close();

    return 0;
}