Cod sursa(job #3372424)

Utilizator IanisCijuCiju Ianis-Cristian IanisCiju Data 3 noiembrie 2026 19:56:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100005;

vector<int> graf[MAXN];
int nivel[MAXN];
int low[MAXN];
stack<int> stiva;
vector<vector<int>> componente_biconexe;

void dfs(int nod, int parinte, int adancime) {
    nivel[nod] = adancime;
    low[nod] = adancime;
    stiva.push(nod);

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

        if (nivel[vecin] > 0) {
            if (nivel[vecin] < low[nod]) {
                low[nod] = nivel[vecin];
            }
        } else {
            dfs(vecin, nod, adancime + 1);

            if (low[vecin] < low[nod]) {
                low[nod] = low[vecin];
            }

            if (low[vecin] >= nivel[nod]) {
                vector<int> comp;
                int nod_extras;

                do {
                    nod_extras = stiva.top();
                    stiva.pop();
                    comp.push_back(nod_extras);
                } while (nod_extras != vecin);

                comp.push_back(nod);
                componente_biconexe.push_back(comp);
            }
        }
    }
}

int main() {
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    int n, m;
    f >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int u, v;
        f >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }

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

    g << componente_biconexe.size() << "\n";

    for (int i = 0; i < componente_biconexe.size(); ++i) {
        for (int j = componente_biconexe[i].size() - 1; j >= 0; --j) {
            g << componente_biconexe[i][j] << " ";
        }
        g << "\n";
    }

    f.close();
    g.close();

    return 0;
}