Cod sursa(job #3372725)

Utilizator bajuuuuBajenaru Mihai Catalin Ionut bajuuuu Data 4 noiembrie 2026 19:38:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m;
vector<vector<int>> listadj;
vector<int> tin, low;
vector<pair<int, int>> stiva;
vector<vector<int>> comp_biconexe;
int timer = 0;
void dfs(int nod, int parent = -1) {
    timer++;
    tin[nod] = low[nod] = timer;
    for (int x : listadj[nod]) {
        if (tin[x] != 0) {
            low[nod] = min(low[nod], tin[x]);
            if (tin[x] < tin[nod]) {
                stiva.push_back({nod, x});
            }
        } else {
            stiva.push_back({nod, x});
            dfs(x, nod);
            low[nod] = min(low[nod], low[x]);
            if (low[x] >= tin[nod]) {
                vector<int> comp;
                while (true) {
                    auto muchie = stiva.back();
                    stiva.pop_back();
                    comp.push_back(muchie.first);
                    comp.push_back(muchie.second);
                    if (muchie == make_pair(nod, x)) break;
                }
                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end());
                comp_biconexe.push_back(comp);
            }
        }
    }
}
int main() {

    in >> n >> m;
    listadj.resize(n + 1);
    tin.resize(n + 1);
    low.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        in >> u >> v;
        listadj[u].push_back(v);
        listadj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!tin[i]) {
            dfs(i);
        }
    }
    out << comp_biconexe.size() << '\n';
    for (auto comp : comp_biconexe) {
        for (int nod : comp) {
            out << nod << ' ';
        }
        out << '\n';
    }
    return 0;
}