Cod sursa(job #3295759)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 8 mai 2025 11:17:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>

std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");

const int MAX_N = 100000;

int n, m;
std::vector<int> g[MAX_N + 1];

int tin[MAX_N + 1];
int low[MAX_N + 1];
int tmr;
int stk[MAX_N + 1], sz;

std::vector<std::vector<int>> componente;

void dfs(int node, int dad) {
    tin[node] = ++tmr;
    low[node] = tin[node];

    stk[++sz] = node;

    for (auto it : g[node]) {
        if (it == dad) continue;
        if (tin[it]) {
            low[node] = std::min(low[node], tin[it]);
        } else {
            dfs(it, node);
            low[node] = std::min(low[node], low[it]);

            if (low[it] >= tin[node]) {
                std::vector<int> comp;

                while (sz > 0 && stk[sz] != it) {
                    comp.push_back(stk[sz]);
                    sz--;
                }

                comp.push_back(it);
                sz--;
                comp.push_back(node);

                componente.push_back(comp);
            }

        }
    }
}

void solve() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

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

    for (auto & it : componente) {
        for (int x : it) {
            fout << x << ' ';
        }
        fout << '\n';
    }
}

int main() {
    solve();
    return 0;
}