Cod sursa(job #2818175)

Utilizator lucamLuca Mazilescu lucam Data 15 decembrie 2021 14:53:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <bits/stdc++.h>

#ifdef ONLINE_JUDGE
    #define in std::cin
    #define out std::cout
#else
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
#endif

template<typename T, size_t N>
constexpr size_t length_of(T (&)[N]) {
    return N;
}

template<typename T>
using Vec = std::vector<T>;
template<typename T, typename U>
using Pair = std::pair<T, U>;
template<typename F>
using Func = std::function<F>;
using i64 = int64_t;
using u64 = uint64_t;
using i8 = char;
using u8 = unsigned char;
template<typename T>
T update_min(T &min, T val) {
    return min = std::min(min, val);
}
template<typename T>
T update_max(T &max, T val) {
    return max = std::max(max, val);
}

constexpr int N = 1e5 + 1;

struct Graph {
    int n;
    Vec<int> nodes[N];
    void add_edge(int u, int v);
    Vec<Vec<int>> biconnected_components();
    struct NodeTimes {
        int in[N];
        int min[N];
    } t;
} g;

void Graph::add_edge(int u, int v) {
    nodes[u].push_back(v);
    nodes[v].push_back(u);
}

Vec<Vec<int>> Graph::biconnected_components() {
    Vec<Vec<int>> res;
    res.reserve(n);
    std::stack<int> dfs_stack;
    auto add_component = [&](int from, int to) {
        res.emplace_back();
        auto &comp = res.back();
        while (dfs_stack.top() != to) {
            comp.push_back(dfs_stack.top());
            dfs_stack.pop();
        }
        comp.push_back(to);
        dfs_stack.pop();
        comp.push_back(from);
    };
    Func<void(int, int)> dfs = [&](int u, int parent) {
        static int ct;
        t.min[u] = t.in[u] = ++ct;
        dfs_stack.push(u);
        for (int v : nodes[u]) {
            if (t.in[v] == 0) {
                dfs(v, u);
                update_min(t.min[u], t.min[v]);
                if (t.min[v] >= t.in[u]) {
                    add_component(u, v);
                }
            } else if (v != parent) {
                update_min(t.min[u], t.in[v]);
            }
        }
    };
    for (int u = 1; u <= n; ++u) {
        if (t.in[u] == 0) {
            dfs(u, 0);
        }
    }
    return res;
}

int main() {
    int m;
    in >> g.n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        in >> u >> v;
        g.add_edge(u, v);
    }
    auto res = g.biconnected_components();
    out << res.size() << '\n';
    for (auto &comp : res) {
        for (auto u : comp) {
            out << u << ' ';
        }
        out << '\n';
    }
}