Cod sursa(job #3373880)

Utilizator ilinca_onofreiIlinca-Ioana Onofrei ilinca_onofrei Data 8 noiembrie 2026 00:13:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int MAXN = 100005;
vector<int> lista_adiacenta[MAXN];

int timp_descoperire[MAXN];     // momentul la care a fost vizitat nodul
int timp_minim_accesibil[MAXN]; // cel mai mic timp la care se poate ajunge din subarbore
int timp;
vector<pair<int, int>> stiva_muchii;
vector<vector<int>> lista_componente_biconexe;

void dfs(int nod_curent, int parinte = 0) {
    timp_descoperire[nod_curent] = timp_minim_accesibil[nod_curent] = ++timp;

    for (int vecin : lista_adiacenta[nod_curent]) {
        if (vecin == parinte) continue;

        if (timp_descoperire[vecin]) {
            // muchie de intoarcere (vecinul a fost deja vizitat)
            timp_minim_accesibil[nod_curent] = min(timp_minim_accesibil[nod_curent], timp_descoperire[vecin]);
            if (timp_descoperire[vecin] < timp_descoperire[nod_curent]) {
                stiva_muchii.push_back({nod_curent, vecin});
            }
        } else {
            // muchie de arbore DFS (nodul vecin este nou)
            stiva_muchii.push_back({nod_curent, vecin});
            dfs(vecin, nod_curent);

            timp_minim_accesibil[nod_curent] = min(timp_minim_accesibil[nod_curent], timp_minim_accesibil[vecin]);

            // daca vecinul nu are drum spre un stramos al lui nod_curent extrag o componenta biconexa
            if (timp_minim_accesibil[vecin] >= timp_descoperire[nod_curent]) {
                vector<int> componenta_curenta;
                while (true) {
                    pair<int, int> muchie = stiva_muchii.back();
                    stiva_muchii.pop_back();

                    componenta_curenta.push_back(muchie.first);
                    componenta_curenta.push_back(muchie.second);

                    if (muchie == make_pair(nod_curent, vecin)) {
                        break;
                    }
                }

                // elim duplicatele
                sort(componenta_curenta.begin(), componenta_curenta.end());
                componenta_curenta.erase(unique(componenta_curenta.begin(), componenta_curenta.end()), componenta_curenta.end());
                lista_componente_biconexe.push_back(componenta_curenta);
            }
        }
    }
}

int main() {
    int n, m;
    if (!(fin >> n >> m)) return 0;

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

    for (int i = 1; i <= n; ++i) {
        if (!timp_descoperire[i]) {
            dfs(i);
        }
    }
    
    fout << lista_componente_biconexe.size() << "\n";
    for (const auto& comp : lista_componente_biconexe) {
        for (size_t i = 0; i < comp.size(); ++i) {
            fout << comp[i] << (i + 1 == comp.size() ? "" : " ");
        }
        fout << "\n";
    }

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