Cod sursa(job #3372679)

Utilizator FilipbosBogdan Filip Filipbos Data 4 noiembrie 2026 18:00:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.81 kb
#include <fstream>
#include <vector>
#include <stack>

std::vector<std::vector<int>> adj; // lista adiacenta
std::vector<bool> viz; // flag de vizitare
std::vector<int> niv; // nivelul unui nod
std::vector<int> niv_min; // nivelul minim la care poate ajunge un nod
std::vector<std::vector<int>> comp_biconexe; // rezultatul final,comp biconexe
int nr_comp_bic; // numarul componentelor biconexe, INDENTARE DE LA 1!!
std::stack<std::pair<int,int>> muchii; // nodurile parcurse in ordinea dfs ului

std::ifstream f("biconex.in");
std::ofstream g("biconex.out");

void constructieCompBic(int x, int y) {
    nr_comp_bic++; // am descoperit o noua comp biconexa
    int i,j;
    do {
        i = muchii.top().first; // tatal
        j = muchii.top().second; // fiul

        comp_biconexe[nr_comp_bic].push_back(j); // adaugam pe rand nodurile care ii apartin,pana la cel critic
        muchii.pop();
    }while (i != x || j != y);
    comp_biconexe[nr_comp_bic].push_back(i); // adaugam nodul critic
}

void golireMuchii() {
    nr_comp_bic++; // am descoperit o noua comp biconexa
    int i,j;
    while (!muchii.empty()) {
        i = muchii.top().first; // tatal
        j = muchii.top().second; // fiul

        comp_biconexe[nr_comp_bic].push_back(j); // adaugam pe rand nodurile care ii apartin,pana la cel critic
        muchii.pop();
    }
    comp_biconexe[nr_comp_bic].push_back(i); // adaugam nodul critic
}

void DFS(int i,int tata) {
    viz[i] = true;
    niv[i] = niv[tata] + 1;
    niv_min[i] = niv[i];
    int copii = 0; // pt tratarea radacinii

    for (int j : adj[i]) {
        copii++;

        if (!viz[j]) {
            muchii.emplace(i,j); // adaug muchie din arborele dfs
            DFS(j,i);

            niv_min[i] = std::min(niv_min[i],niv_min[j]);

            if (tata != 0 && niv_min[j] >= niv[i]) // i e nod critic
                constructieCompBic(i,j); // pasam nodul critic si fiul ca argumente
            if (tata == 0 && copii > 1)
                constructieCompBic(i,j);
        }
        else if (j != tata)
            niv_min[i] = std::min(niv_min[i],niv[j]);
        //daca avem o muchie de intoarcere
    }
}

int main() {
    int n,m;
    f >> n >> m;
    adj.resize(n+1);
    viz.resize(n+1);
    niv.resize(n+1);
    niv_min.resize(n+1);
    comp_biconexe.resize(n+1);

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

    for (int i = 1; i <= n; i++) {
        if (!viz[i])
            DFS(i,0);
    }

    if (!muchii.empty())
        golireMuchii();

    g << nr_comp_bic << '\n';

    for (int i = 1; i <= nr_comp_bic; i++) {
        for (int j : comp_biconexe[i])
            g << j << ' ';
        g << '\n';
    }

    return 0;
}