Cod sursa(job #3374398)

Utilizator luizaaaDutu Luiza-Alexandra luizaaa Data 8 noiembrie 2026 23:47:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

const int MAX_NODURI = 100005;

vector<int> graf[MAX_NODURI];

int nivel_descoperire[MAX_NODURI];
int cel_mai_sus_ajuns[MAX_NODURI];
int timp_curent = 0;

stack<pair<int, int>> stiva_muchii;

vector<vector<int>> componente_biconexe;

void gaseste_biconexe(int nod, int parinte) {
    timp_curent++;
    nivel_descoperire[nod] = timp_curent;
    cel_mai_sus_ajuns[nod] = timp_curent;

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

        if (nivel_descoperire[vecin] > 0) {
            cel_mai_sus_ajuns[nod] = min(cel_mai_sus_ajuns[nod], nivel_descoperire[vecin]);

            if (nivel_descoperire[vecin] < nivel_descoperire[nod]) {
                 stiva_muchii.push({nod, vecin});
            }
        } else {
            stiva_muchii.push({nod, vecin});
            gaseste_biconexe(vecin, nod);

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

            if (cel_mai_sus_ajuns[vecin] >= nivel_descoperire[nod]) {
                vector<int> componenta_noua;
                set<int> noduri_unice;

                while (true) {
                    pair<int, int> muchie = stiva_muchii.top();
                    stiva_muchii.pop();
                    
                    noduri_unice.insert(muchie.first);
                    noduri_unice.insert(muchie.second);
                    
                    if (muchie.first == nod && muchie.second == vecin) {
                        break;
                    }
                }

                for (int n : noduri_unice) {
                    componenta_noua.push_back(n);
                }
                componente_biconexe.push_back(componenta_noua);
            }
        }
    }
}

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

    int numar_noduri, numar_muchii;
    fin >> numar_noduri >> numar_muchii;

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

    for (int i = 1; i <= numar_noduri; ++i) {
        if (nivel_descoperire[i] == 0) {
            gaseste_biconexe(i, 0);
        }
    }

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

    return 0;
}