Cod sursa(job #3374262)

Utilizator dcamaximDuca Maxim dcamaxim Data 8 noiembrie 2026 21:26:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n, m, timer;
vector<vector<int>> adj;
vector<int> nivel, niv_min;
vector<vector<int>> solutii;
stack<pair<int, int>> stiva;

void dfs(int nod, int tata = 0) {
    nivel[nod] = niv_min[nod] = ++timer;
    int fii = 0;

    for (int vecin : adj[nod]) {
        if (vecin == tata) continue;

        if (nivel[vecin]) {
            niv_min[nod] = min(niv_min[nod], nivel[vecin]);
            if (nivel[vecin] < nivel[nod]) {
                stiva.push({nod, vecin});
            }
        } else {
            fii++;
            stiva.push({nod, vecin});
            dfs(vecin, nod);
            niv_min[nod] = min(niv_min[nod], niv_min[vecin]);

            if (niv_min[vecin] >= nivel[nod]) {
                vector<int> comp;
                while (true) {
                    auto muchie = stiva.top();
                    stiva.pop();
                    comp.push_back(muchie.first);
                    comp.push_back(muchie.second);
                    if (muchie.first == nod && muchie.second == vecin) {
                        break;
                    }
                }
                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end());
                solutii.push_back(comp);
            }
        }
    }
}

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

    fin >> n >> m;
    adj.resize(n + 1);
    nivel.assign(n + 1, 0);
    niv_min.assign(n + 1, 0);

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

    for (int i = 1; i <= n; ++i) {
        if (!nivel[i]) {
            dfs(i);
        }
    }

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

    return 0;
}