Cod sursa(job #3375044)

Utilizator PedroLuisNegoita Luis PedroLuis Data 9 noiembrie 2026 23:53:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100005;

vector<int> graf[MAXN];
int tin[MAXN], low[MAXN];
int timer;
stack<int> st;
vector<vector<int>> bcc;

void dfs(int nod, int tata = 0) {
    tin[nod] = low[nod] = ++timer;
    st.push(nod);

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

        if (tin[vecin]) {
            low[nod] = min(low[nod], tin[vecin]);
        } else {
            dfs(vecin, nod);
            
            low[nod] = min(low[nod], low[vecin]);

            if (low[vecin] >= tin[nod]) {
                vector<int> componenta;
                int extras;
                do {
                    extras = st.top();
                    st.pop();
                    componenta.push_back(extras);
                } while (extras != vecin);
                
                componenta.push_back(nod);
                bcc.push_back(componenta);
            }
        }
    }
}

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

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

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

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

    fout << bcc.size() << "\n";
    for (auto comp : bcc) {
        for (int nod : comp) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    return 0;
}