Cod sursa(job #3374466)

Utilizator mariatutaTuta Maria Alexandra mariatuta Data 9 noiembrie 2026 00:59:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int max_n = 100005;

vector<int> adj[max_n];
int nivel[max_n], low[max_n];
stack<int> st;
int timer = 0;

vector<vector<int>> rez;

void dfs(int u, int tata = 0) {
    // init timpi
    nivel[u] = low[u] = ++timer;
    st.push(u);

    for (int v : adj[u]) {
        if (v == tata) continue;

        if (nivel[v]) {
            // muchie de intoarcere
            low[u] = min(low[u], nivel[v]);
        } else {
            // nod nevizitat
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            // verificare conditie biconexitate
            if (low[v] >= nivel[u]) {
                vector<int> comp;
                int nod;

                // extragem componenta din stiva
                do {
                    nod = st.top();
                    st.pop();
                    comp.push_back(nod);
                } while (nod != v); // ne oprim la v

                // u face parte din componenta, dar ramane in stiva
                // pt alte posibile componente biconexe
                comp.push_back(u);
                rez.push_back(comp);
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;

    // citire graf neorientat
    for (int i = 0; i < m; ++i) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

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

    // afisare nr componente biconexe
    fout << rez.size() << "\n";

    // afisare noduri per componenta
    for (auto& comp : rez) {
        for (int nod : comp) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}