Cod sursa(job #3372045)

Utilizator zamhoriaHoria Zamfir zamhoria Data 2 noiembrie 2026 13:50:59
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

int n, m;
int timer = 0; // contor global pt tin

vector<int> tin; // time in, marcam momentul in dfs cand ajungem pentru prima oara la un nod
vector<bool> viz;
vector<int> low; // timpul cel mai mic din arborele dfs la care se poate intoarce nodul i / sau oricare dintre fii sai, pentru low[i]
vector<vector<int>> graf;
vector<vector<int>> componente; // vector ce tine componentele biconexe
stack<int> componenta_curenta; // stack global, tinem componenta biconexa la momentul curent in dfs

void dfs(int s, int parinte) {
    viz[s] = true;

    // initializam time in si low pt nodul curent si il punem in componenta curenta
    tin[s] = low[s] = ++timer;
    componenta_curenta.push(s);

    for (auto vecin : graf[s]) {
        if (vecin == parinte) continue; // trecem peste parinte

        if (viz[vecin]) { // daca e deja vizitat -> am gasit o muchie de intoarcere
            low[s] = min(low[s], tin[vecin]);
        }else {
            // nu a fost inca vizitat
            dfs(vecin, s);

            low[s] = min(low[s], low[vecin]); // actualizam cu valoarea fiului


            if (low[vecin] >= tin[s]) { // am terminat componenta curenta biconexa, scoatem din stiva toate nodurile
                vector<int> componenta;

                // am ajuns la o componenta biconexa completa
                // scoatem toate nodurile din stiva pana la vecin, inclusiv, dar nu si punctul critic s
                // deoarece ar putea fi parte din alte componente biconexe

                while (componenta_curenta.top() != vecin) {
                    componenta.push_back(componenta_curenta.top());
                    componenta_curenta.pop();
                }

                componenta.push_back(componenta_curenta.top());
                componenta_curenta.pop();
                componenta.push_back(s);

                componente.push_back(componenta);
            }
        }
    }
}

int main() {

    cin >> n >> m;

    tin.resize(n + 1);
    low.resize(n + 1);
    viz.assign(n + 1, false);
    graf.resize(n + 1);

    for (int i = 1; i <= m; i++) {
        int n1, n2;

        cin >> n1 >> n2;

        graf[n1].push_back(n2);
        graf[n2].push_back(n1);
    }

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

    cout << componente.size() << '\n';

    for (auto componenta : componente) {
        for (auto elem : componenta)
            cout << elem << ' ';

        cout << '\n';
    }

}