test/src/graph/biconnected_components/biconnected_components.test.cpp

View this file on GitHub
Last update: 2024-01-30 20:12:06+09:00
Problem: https://judge.yosupo.jp/problem/biconnected_components

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components"

#include <iostream>

#include "library/graph/biconnected_components.hpp"

using suisen::BiconnectedComponents;

auto solve1(int n, std::vector<std::pair<int, int>> edges) {
    BiconnectedComponents bcc(n, edges);
    return std::make_pair(bcc.component_num(), bcc.components());
}

auto solve2(int n, std::vector<std::pair<int, int>> edges) {
    BiconnectedComponents bcc(n);
    for (const auto &[u, v] : edges) bcc.add_edge(u, v);
    bcc.build();
    return std::make_pair(bcc.component_num(), bcc.components());
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> edges(m);
    for (auto &[u, v] : edges) {
        std::cin >> u >> v;
    }
    
    auto ans1 = solve1(n, edges);
    auto ans2 = solve2(n, edges);
    assert(ans1 == ans2);

    const auto &[comp_num, components] = ans1;

    std::cout << comp_num << '\n';
    for (const auto &component : components) {
        std::cout << component.vids.size();
        for (const int v : component.vids) std::cout << ' ' << v;
        std::cout << '\n';
    }

    return 0;
}

#line 1 "test/src/graph/biconnected_components/biconnected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components"

#include <iostream>

#line 1 "library/graph/biconnected_components.hpp"



#include <cstdint>
#include <utility>
#line 1 "library/graph/low_link.hpp"



#include <cassert>
#include <cstddef>
#line 8 "library/graph/low_link.hpp"
#include <vector>

namespace suisen {
    struct LowLink {
        LowLink() : LowLink(0) {}
        LowLink(const int n) : _n(n), _m(0), _g(n), _pre_order(n, -1), _low_link(n), _built(false), _conn_comp_num(0), _par(n, -1) {}
        LowLink(const int n, const std::vector<std::pair<int, int>> &edges) : LowLink(n) {
            for (const auto &[u, v] : edges) add_edge(u, v);
            build();
        }
        
        // Add an edge and return its ID. IDs are assigned in the order (0,1,2, ...).
        int add_edge(int u, int v) {
            _built = false;
            _edges.emplace_back(u, v);
            _g[u].emplace_back(v, _m);
            _g[v].emplace_back(u, _m);
            return _m++;
        }

        void build() {
            dfs_for_all_connected_components();
            _built = true;
        }

        int vertex_num() const { return _n; }
        int edge_num()   const { return _m; }

        const std::pair<int, int>& edge(int edge_id) const { return _edges[edge_id]; }
        const std::vector<std::pair<int, int>>& edges() const { return _edges; }
        // list of edges { u, edge_id } adjacent to the vertex v.
        const std::vector<std::pair<int, int>>& operator[](int v) const { return _g[v]; }
        
        int pre_order(int v) const {
            assert(_built);
            return _pre_order[v];
        }
        int low_link(int v) const {
            assert(_built);
            return _low_link[v];
        }

        // Returns IDs of bridges.
        const std::vector<int>& bridge_ids() const {
            assert(_built);
            return _bridges;
        }
        const std::vector<int>& articulation_points() const {
            assert(_built);
            return _articulation_points;
        }

        // O(1)
        // Assuming that there exists the edge {u,v}, return whether the edge is a bridge or not.
        bool is_bridge(int u, int v) const {
            assert(_built);
            if (_pre_order[u] > _pre_order[v]) std::swap(u, v);
            // u is an ancestor of v
            return _pre_order[u] < _low_link[v];
        }

        // O(# edges incident with u)
        // Return whether the vertex is a articulation point or not.
        bool is_articulation_point(int u) const {
            assert(_built);
            return connected_component_num_if_removed(u) > connected_component_num();
        }

        // Return the number of connected components
        int connected_component_num() const {
            assert(_built);
            return _conn_comp_num;
        }

        // O(1)
        // Assuming that there exists the edge {u,v}, return the number of connected components of the graph obtained by removing an edge {u,v}.
        // If there are multiple edges {u,v}, consider removing only one of them.
        int connected_component_num_if_removed(int u, int v) const {
            assert(_built);
            return _conn_comp_num + is_bridge(u, v);
        }

        // O(# edges incident with u)
        // Return the number of connected components of the graph obtained by removing an vertex u and edges incident with it.
        int connected_component_num_if_removed(int u) const {
            assert(_built);
            static std::vector<int8_t> seen;
            if (seen.size() < size_t(_n)) seen.resize(_n);
            bool is_root = true;
            int res = 0;
            for (const auto& [v, _] : _g[u]) {
                if (_pre_order[v] < _pre_order[u]) {
                    is_root = false;
                    continue;
                }
                if (_par[v] == u and not std::exchange(seen[v], true)) {
                    res += (_pre_order[u] <= _low_link[v]);
                }
            }
            // rollback
            for (const auto& [v, _] : _g[u]) seen[v] = false;
            return _conn_comp_num - 1 + res + (not is_root);
        }
    protected:
        int _n, _m;
        // list of edges
        std::vector<std::pair<int, int>> _edges;
        // vertex -> list of (adjacent vertex, edge id)
        std::vector<std::vector<std::pair<int, int>>> _g;
        // vertex -> pre order
        std::vector<int> _pre_order;
        std::vector<int> _low_link;
        // list of ids of bridges
        std::vector<int> _bridges;
        std::vector<int> _articulation_points;

        bool _built;

    private:
        // # connected components
        int _conn_comp_num;
        std::vector<int> _par;

        void dfs(const int u, const int prev_id, int& ord) {
            const bool is_root = prev_id < 0;
            bool is_articulation_point = false;
            int ch_cnt = 0;
            _pre_order[u] = _low_link[u] = ord++;
            for (const auto& [v, id] : _g[u]) if (id != prev_id) {
                if (_pre_order[v] < 0) {
                    _par[v] = u;
                    ++ch_cnt;
                    dfs(v, id, ord);
                    _low_link[u] = std::min(_low_link[u], _low_link[v]);
                    if (_pre_order[u] <= _low_link[v]) {
                        is_articulation_point = not is_root;
                        if (_pre_order[u] != _low_link[v]) _bridges.push_back(id);
                    }
                } else {
                    _low_link[u] = std::min(_low_link[u], _pre_order[v]);
                }
            }
            if (is_articulation_point or (is_root and ch_cnt > 1)) _articulation_points.push_back(u);
        }

        void dfs_for_all_connected_components() {
            for (int i = 0, ord = 0; i < _n; ++i) if (_pre_order[i] < 0) {
                dfs(i, -1, ord);
                ++_conn_comp_num;
            }
        }
    };
} // namespace suisen



#line 7 "library/graph/biconnected_components.hpp"

namespace suisen {
    struct BiconnectedComponents : public LowLink {
        BiconnectedComponents() 
            : BiconnectedComponents(0) {}
        BiconnectedComponents(const int n) 
            : LowLink(n), _used(_n, false), _edge_comp_id(_m, -1), _edge_comp_num(0) {}
        BiconnectedComponents(const int n, const std::vector<std::pair<int, int>> &edges) 
            : LowLink(n, edges), _used(_n, false), _edge_comp_id(_m, -1), _edge_comp_num(0) {
            dfs_for_all_connected_components();
        }

        void build() {
            LowLink::build();
            dfs_for_all_connected_components();
        }

        // # of component (including isolated vertices)
        int component_num() const {
            assert(_built);
            return _edge_comp_num + _isolated_vertices.size();
        }
        // component_num() - # of isolated vertices
        int edge_component_num() const {
            assert(_built);
            return _edge_comp_num;
        }
        int isolated_vertex_num() const {
            assert(_built);
            return _isolated_vertices.size();
        }
        bool is_isolated_component(int component_id) const {
            return component_id >= _edge_comp_num;
        } 

        int operator[](int edge_id) const {
            assert(_built);
            return _edge_comp_id[edge_id];
        }

        const std::vector<int>& isolated_vertices() const {
            assert(_built);
            return _isolated_vertices;
        }

        struct Subgraph {
            std::vector<int> vids, eids;
            int vertex_num() const { return vids.size(); }
            int edge_num()   const { return eids.size(); }
            const std::vector<int>& vertex_set() const { return vids; }
            const std::vector<int>& edge_set()   const { return eids; }
            bool operator==(const Subgraph &rhs) const { return vids == rhs.vids and eids == rhs.eids; }
            bool operator!=(const Subgraph &rhs) const { return not (*this == rhs); }
        };
        
        // vector of biconnected components. [0:edge_component_num()) has edges, [edge_component_num(),component_num()) are isolated vertices.
        std::vector<Subgraph> components() const {
            assert(_built);
            std::vector<Subgraph> res(component_num());
            for (int i = 0; i < _m; ++i) {
                res[_edge_comp_id[i]].eids.push_back(i);
            }
            std::vector<int8_t> seen(vertex_num(), false);
            for (int id = 0; id < _edge_comp_num; ++id) {
                for (int eid : res[id].eids) {
                    const auto &[u, v] = edge(eid);
                    if (not std::exchange(seen[u], true)) res[id].vids.push_back(u);
                    if (not std::exchange(seen[v], true)) res[id].vids.push_back(v);
                }
                for (int eid : res[id].eids) {
                    const auto &[u, v] = edge(eid);
                    seen[u] = seen[v] = false;
                }
            }
            int id = _edge_comp_num;
            for (int v : _isolated_vertices) {
                res[id++].vids = { v };
            }
            return res;
        }

    private:
        std::vector<int8_t> _used;
        std::vector<int> _edge_comp_id;
        int _edge_comp_num;
        std::vector<int> _isolated_vertices;

        void dfs(int u, int par_edge_id) {
            _used[u] = true;
            static std::vector<int> edges;
            for (const auto &[v, edge_id] : _g[u]) if (edge_id != par_edge_id) {
                // edge_id is a new edge
                if (not _used[v] or _pre_order[v] < _pre_order[u]) edges.push_back(edge_id);
                // v is not a new vertex
                if (_used[v]) continue;
                dfs(v, edge_id);
                if (_low_link[v] < _pre_order[u]) continue;
                int e;
                do _edge_comp_id[e = edges.back()] = _edge_comp_num, edges.pop_back(); while (e != edge_id);
                _edge_comp_num++;
            }
        }
        void dfs_for_all_connected_components() {
            _edge_comp_num = 0;
            _edge_comp_id.assign(_m, -1);
            _used.assign(_n, false);
            for (int i = 0; i < _n; ++i) if (not _used[i]) {
                dfs(i, -1);
                if (_g[i].empty()) _isolated_vertices.push_back(i);
            }
        }
    };
} // namespace suisen



#line 6 "test/src/graph/biconnected_components/biconnected_components.test.cpp"

using suisen::BiconnectedComponents;

auto solve1(int n, std::vector<std::pair<int, int>> edges) {
    BiconnectedComponents bcc(n, edges);
    return std::make_pair(bcc.component_num(), bcc.components());
}

auto solve2(int n, std::vector<std::pair<int, int>> edges) {
    BiconnectedComponents bcc(n);
    for (const auto &[u, v] : edges) bcc.add_edge(u, v);
    bcc.build();
    return std::make_pair(bcc.component_num(), bcc.components());
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> edges(m);
    for (auto &[u, v] : edges) {
        std::cin >> u >> v;
    }
    
    auto ans1 = solve1(n, edges);
    auto ans2 = solve2(n, edges);
    assert(ans1 == ans2);

    const auto &[comp_num, components] = ans1;

    std::cout << comp_num << '\n';
    for (const auto &component : components) {
        std::cout << component.vids.size();
        for (const int v : component.vids) std::cout << ' ' << v;
        std::cout << '\n';
    }

    return 0;
}