Cod sursa(job #2869827)

Utilizator the_horoHorodniceanu Andrei the_horo Data 11 martie 2022 21:05:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <vector>
#include <stack>


using u32 = uint32_t;
using i32 = int32_t;

constexpr size_t MAX_NODES = 100000;


std::array<std::vector<size_t>, MAX_NODES> edges;

std::array<size_t, MAX_NODES> level;
std::array<size_t, MAX_NODES> low;

std::vector<std::vector<size_t>> result;

std::array<bool, MAX_NODES> viz;
std::stack<size_t> order;
void dfs (size_t node, size_t parent) {
    viz[node] = true;
    low[node] = level[node];
    order.emplace(node);

    for (auto to: edges[node]) {
        if (to == parent)
            continue;

        if (viz[to]) {
            low[node] = std::min(low[node], level[to]);
            continue;
        }

        level[to] = level[node] + 1;
        dfs(to, node);

        low[node] = std::min(low[node], low[to]);


        if (level[node] <= low[to]) {
            /* critical edge */
        }

        if (level[node] == low[node]) {
            /* articulation point */
        }


        if (level[node] == low[node] || level[node] <= low[to]) {
            result.emplace_back();

            size_t last;
            do {
                last = order.top();
                order.pop();
                result.back().emplace_back(last);
            } while (last != to);

            result.back().emplace_back(node);
        }
    }
}

int main () {
    std::ifstream in("biconex.in");
    std::ofstream out("biconex.out");

    size_t nodeCount, edgeCount;
    in >> nodeCount >> edgeCount;

    for (size_t i = 0; i != edgeCount; ++ i) {
        size_t x, y;
        in >> x >> y;
        -- x, -- y;

        edges[x].emplace_back(y);
        edges[y].emplace_back(x);
    }

    dfs(0, -1);

    out << result.size() << '\n';
    for (const auto &component: result) {
        for (const auto &node: component)
            out << node + 1 << ' ';
        out << '\n';
    }
}