Cod sursa(job #3372640)

Utilizator G_DenisaGroza Denisa-Georgiana G_Denisa Data 4 noiembrie 2026 16:04:40
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

//O(m+n)
using namespace std;

vector<vector<int>> matrice;
vector<int> nivel, nma;
vector<bool> viz;
stack<int> S;
vector<vector<int>> biconnected_components;

void dfs(int k, int p) {
    viz[k] = true;
    nivel[k] = (p == 0 ? 1 : nivel[p] + 1);
    nma[k] = nivel[k];
    S.push(k);

    for (int x : matrice[k]) {
        if (x == p) continue;

        if (viz[x]) {
            nma[k] = min(nma[k], nivel[x]);
        } else {
            dfs(x, k);
            nma[k] = min(nma[k], nma[x]);

            if (nivel[k] <= nma[x]) {
                vector<int> comp;
                int node;
                do {
                    node = S.top();
                    S.pop();
                    comp.push_back(node);
                } while (node != x);
                comp.push_back(k);
                biconnected_components.push_back(comp);
            }
        }
    }
}

int main() {
    int n, m;
    ifstream f("biconex.in");
    f >> n >> m;

    matrice.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        f >> u >> v;
        matrice[u].push_back(v);
        matrice[v].push_back(u);
    }
    f.close();

    nivel.resize(n + 1, 0);
    nma.resize(n + 1, 0);
    viz.resize(n + 1, false);

    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            dfs(i, 0);
        }
    }

    ofstream g("biconex.out");
    g << biconnected_components.size() << "\n";
    for (const auto& comp : biconnected_components) {
        for (int node : comp) {
            g << node << " ";
        }
        g << "\n";
    }

    g.close();
    return 0;
}