Cod sursa(job #3374563)

Utilizator anastasia.sAnastasia anastasia.s Data 9 noiembrie 2026 02:19:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

#define NMax 100005

vector<int> g[NMax];
int nivel[NMax];
int low_link[NMax];  // ne va da scurtaturile catre nodurile din care am venit(daca exista)
vector<int> st;
vector<vector<int>> bcc;  // lista in care stocam componentele biconexe
int coborare = 0;         // pentru a stii cat de mult coboram in dfs si unde ne aflam

void dfs(int nod, int parinte) {
    coborare++;

    nivel[nod] = low_link[nod] = coborare;
    st.push_back(nod);

    for (int vecin : g[nod]) {
        if (vecin == parinte)
            continue;

        if (nivel[vecin] > 0)
            low_link[nod] = min(low_link[nod], nivel[vecin]);
        else {
            dfs(vecin, nod);

            low_link[nod] = min(low_link[nod], low_link[vecin]);

            if (low_link[vecin] >= nivel[nod]) {
                vector<int> componenta;
                int extras;

                do {
                    extras = st.back();
                    st.pop_back();
                    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;

    int x, y;
    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

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

    fout << bcc.size() << "\n";
    
    for (auto c : bcc) {
        for (auto el : c) {
            fout << el << " ";
        }
        fout << "\n";
    }

    return 0;
}