Cod sursa(job #3374319)

Utilizator xeneyzeAl Daraghmeh Omar-Sorin xeneyze Data 8 noiembrie 2026 22:39:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <bits/stdc++.h>
using namespace std;

// Ideea: Tarjan cu nivel, low si o stiva de noduri.
// Cand terminam un fiu v al lui u si avem low[v]>=nivel[u],
// inseamna ca v nu poate urca mai sus de u. Atunci scoatem din stiva
// nodurile pana la v inclusiv; impreuna cu u ele formeaza o componenta biconexa.
//
// DFS-ul e scris ITERATIV (cu stiva proprie), pentru ca pe un lant de 100.000
// de noduri varianta recursiva da segmentation fault (se umple stiva programului).

int n, m;
vector<vector<int>> g;
vector<int> nivel, low, it, st;
vector<vector<int>> comp;

void dfs(int rad) {
    // apel = (nod, tata)
    vector<pair<int,int>> apel;
    nivel[rad]=low[rad]=1;
    st.push_back(rad);
    apel.push_back({rad, 0});

    while ( !apel.empty()) {
        int u=apel.back().first, tata=apel.back().second;

        if ( it[u]<(int)g[u].size()) {
            int v=g[u][it[u]++];
            if ( v== tata) continue;
            if ( nivel[v]== 0) {
                // "apelam recursiv" dfs(v, u)
                nivel[v]=low[v]=nivel[u]+1;
                st.push_back(v);
                apel.push_back({v, u});
            } else {
                low[u]=min(low[u], nivel[v]);
            }
        } else {
            // am terminat cu u -> "revenim" in tata
            apel.pop_back();
            if ( tata== 0) continue;
            low[tata]=min(low[tata], low[u]);
            if ( low[u]>=nivel[tata]) {
                comp.push_back({});
                int x;
                do {
                    x=st.back();
                    st.pop_back();
                    comp.back().push_back(x);
                } while ( x!=u);
                comp.back().push_back(tata);
            }
        }
    }
    st.clear();
}

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

    fin>>n>>m;
    g.resize(n+1);
    for ( int i=0; i<m; i++) {
        int a, b;
        fin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    nivel.assign(n+1, 0);
    low.assign(n+1, 0);
    it.assign(n+1, 0);
    for ( int i=1; i<=n; i++)
        if ( nivel[i]== 0) dfs(i);

    fout<<comp.size()<<"\n";
    for ( auto &c : comp) {
        for ( int x : c) fout<<x<<" ";
        fout<<"\n";
    }
    return 0;
}