Cod sursa(job #3374565)

Utilizator cristian___Nastase Cristian-Florin cristian___ Data 9 noiembrie 2026 02:20:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <vector>
#include <fstream>

using namespace std;

vector<vector<int>> lista, componente;
vector<int> nivel, low, stiva;
int timp;

void dfs(int nod) {
    nivel[nod] = low[nod] = ++timp;
    stiva.push_back(nod);

    for (int vecin : lista[nod]) {
        if (nivel[vecin]) {
            low[nod] = min(low[nod], nivel[vecin]);
        } else {
            dfs(vecin);
            low[nod] = min(low[nod], low[vecin]);

            if (low[vecin] >= nivel[nod]) {
                componente.push_back({nod});
                do {
                    componente.back().push_back(stiva.back());
                    stiva.pop_back();
                } while (componente.back().back() != vecin);
            }
        }
    }
}

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

    int n, m, x, y;
    in>>n>>m;

    lista.resize(n + 1);
    nivel.resize(n + 1);
    low.resize(n + 1);

    while (m--) {
        in>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }

    for (int nod = 1; nod <= n; nod++) {
        if (!nivel[nod]) {
            dfs(nod);
        }
    }

    out<<componente.size()<<'\n';

    for (auto& componenta : componente) {
        for (int nod : componenta) {
            out<<nod<<' ';
        }
        out<<'\n';
    }
}