Cod sursa(job #3374098)

Utilizator biancamihaiMihai Maria Bianca biancamihai Data 8 noiembrie 2026 17:44:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.32 kb
#include <bits/stdc++.h>
using namespace std;

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

    int nr_noduri, nr_muchii;
    fin >> nr_noduri >> nr_muchii;

    vector<vector<int>> lista_adiacenta(nr_noduri + 1);
    for (int i = 0; i < nr_muchii; i++) {
        int x, y;
        fin >> x >> y;
        lista_adiacenta[x].push_back(y);
        lista_adiacenta[y].push_back(x);
    }

    vector<int> timp_intrare(nr_noduri + 1, 0);
    vector<int> timp_minim(nr_noduri + 1, 0);
    vector<int> parinte(nr_noduri + 1, 0);
    vector<int> urmatorul_vecin(nr_noduri + 1, 0);
    vector<int> marcaj_componenta(nr_noduri + 1, 0);

    vector<pair<int, int>> stiva_muchii;
    vector<vector<int>> componente_biconexe;
    int contor_timp = 0;

    for (int start = 1; start <= nr_noduri; start++) {
        if (timp_intrare[start]) continue;

        vector<int> stiva_dfs;
        stiva_dfs.push_back(start);
        timp_intrare[start] = timp_minim[start] = ++contor_timp;

        while (!stiva_dfs.empty()) {
            int curent = stiva_dfs.back();

            if (urmatorul_vecin[curent] < (int)lista_adiacenta[curent].size()) {
                int vecin = lista_adiacenta[curent][urmatorul_vecin[curent]++];
                if (vecin == parinte[curent]) continue;

                if (timp_intrare[vecin] == 0) {
                    // muchie de arbore: o punem pe stiva de muchii
                    parinte[vecin] = curent;
                    timp_intrare[vecin] = timp_minim[vecin] = ++contor_timp;
                    stiva_muchii.push_back({curent, vecin});
                    stiva_dfs.push_back(vecin);
                } else if (timp_intrare[vecin] < timp_intrare[curent]) {

                    stiva_muchii.push_back({curent, vecin});
                    timp_minim[curent] = min(timp_minim[curent], timp_intrare[vecin]);
                }
            } else {
                stiva_dfs.pop_back();
                if (stiva_dfs.empty()) continue;

                int tata = stiva_dfs.back();
                timp_minim[tata] = min(timp_minim[tata], timp_minim[curent]);

                if (timp_minim[curent] >= timp_intrare[tata]) {
                    vector<int> componenta;
                    int id = componente_biconexe.size() + 1;
                    pair<int, int> muchie;
                    do {
                        muchie = stiva_muchii.back();
                        stiva_muchii.pop_back();
                        if (marcaj_componenta[muchie.first] != id) {
                            marcaj_componenta[muchie.first] = id;
                            componenta.push_back(muchie.first);
                        }
                        if (marcaj_componenta[muchie.second] != id) {
                            marcaj_componenta[muchie.second] = id;
                            componenta.push_back(muchie.second);
                        }
                    } while (!(muchie.first == tata && muchie.second == curent));
                    componente_biconexe.push_back(componenta);
                }
            }
        }
    }

    fout << componente_biconexe.size() << "\n";
    for (const auto& componenta : componente_biconexe) {
        for (int nod : componenta) fout << nod << " ";
        fout << "\n";
    }
    return 0;
}