cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:warning: Block Cut Forest
(library/graph/block_cut_forest.hpp)

Block Cut Forest

Depends on

Code

#ifndef SUISEN_BLOCK_CUT_FOREST
#define SUISEN_BLOCK_CUT_FOREST

#include "library/graph/remove_multiedges.hpp"
#include "library/graph/biconnected_components.hpp"

namespace suisen {
    struct BlockCutForest {
        BlockCutForest() = default;
        BlockCutForest(const BiconnectedComponents &bcc)
            : _edge_comp_num(bcc.edge_component_num()), _isolated_vertex_num(bcc.isolated_vertex_num()), _art_num(bcc.articulation_points().size()), _node_num(_edge_comp_num + _isolated_vertex_num + _art_num), _g(_node_num), _vertex_num(_node_num), _comp_id(bcc.vertex_num(), -1) {
            std::vector<int> art_id(bcc.vertex_num(), -1);
            int next_id = _edge_comp_num + _isolated_vertex_num;
            for (int v : bcc.articulation_points()) art_id[v] = next_id++;

            for (int edge_id = 0; edge_id < bcc.edge_num(); ++edge_id) {
                const int cid = bcc[edge_id];
                const auto &[u, v] = bcc.edge(edge_id);
                _comp_id[u] = _comp_id[v] = cid;
                if (int vid = art_id[u]; vid >= 0) _g[vid].push_back(cid), _g[cid].push_back(vid);
                if (int vid = art_id[v]; vid >= 0) _g[vid].push_back(cid), _g[cid].push_back(vid);
            }
            int isolated_vertex_id = _edge_comp_num;
            for (int v : bcc.isolated_vertices()) {
                _comp_id[v] = isolated_vertex_id++;
            }

            remove_multiedges(_g);

            for (int v = 0; v < bcc.vertex_num(); ++v) {
                if (int vid = art_id[v]; vid < 0) {
                    ++_vertex_num[_comp_id[v]];
                } else {
                    _vertex_num[vid] = 1;
                    for (int cid : _g[vid]) ++_vertex_num[cid];
                }
            }
        }

        int size() const { return _edge_comp_num + _isolated_vertex_num + _art_num; }
        
        bool is_articulation_point(int id)    const { return id >= _edge_comp_num + _isolated_vertex_num; }
        bool is_biconnected_component(int id) const { return not is_articulation_point(id); }
        bool is_isolated_vertex(int id)       const { return id >= _edge_comp_num and is_biconnected_component(id); }

        const std::vector<int>& operator[](int id) const { return _g[id]; }
        std::vector<int>& operator[](int id) { return _g[id]; }

        int vertex_num(int id) const { return _vertex_num[id]; }

        int component_id(int vertex) const {
            return _comp_id[vertex];
        }

    private:
        int _edge_comp_num;
        int _isolated_vertex_num;
        int _art_num;
        int _node_num;
        std::vector<std::vector<int>> _g;
        std::vector<int> _vertex_num;
        std::vector<int> _comp_id;
    };
} // namespace suisen


#endif // SUISEN_BLOCK_CUT_FOREST
#line 1 "library/graph/block_cut_forest.hpp"



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



#include <algorithm>
#include <vector>
#include <cstdint>

namespace suisen {

void remove_multiedges(std::vector<std::vector<int>> &g) {
    std::vector<uint8_t> exists(g.size(), 0);
    for (auto &vs : g) {
        for (int v : vs) exists[v] = true;
        vs.erase(std::remove_if(vs.begin(), vs.end(), [&](int v) { return not std::exchange(exists[v], false); }), vs.end());
    }
}

} // namespace suisen



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



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



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

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 "library/graph/block_cut_forest.hpp"

namespace suisen {
    struct BlockCutForest {
        BlockCutForest() = default;
        BlockCutForest(const BiconnectedComponents &bcc)
            : _edge_comp_num(bcc.edge_component_num()), _isolated_vertex_num(bcc.isolated_vertex_num()), _art_num(bcc.articulation_points().size()), _node_num(_edge_comp_num + _isolated_vertex_num + _art_num), _g(_node_num), _vertex_num(_node_num), _comp_id(bcc.vertex_num(), -1) {
            std::vector<int> art_id(bcc.vertex_num(), -1);
            int next_id = _edge_comp_num + _isolated_vertex_num;
            for (int v : bcc.articulation_points()) art_id[v] = next_id++;

            for (int edge_id = 0; edge_id < bcc.edge_num(); ++edge_id) {
                const int cid = bcc[edge_id];
                const auto &[u, v] = bcc.edge(edge_id);
                _comp_id[u] = _comp_id[v] = cid;
                if (int vid = art_id[u]; vid >= 0) _g[vid].push_back(cid), _g[cid].push_back(vid);
                if (int vid = art_id[v]; vid >= 0) _g[vid].push_back(cid), _g[cid].push_back(vid);
            }
            int isolated_vertex_id = _edge_comp_num;
            for (int v : bcc.isolated_vertices()) {
                _comp_id[v] = isolated_vertex_id++;
            }

            remove_multiedges(_g);

            for (int v = 0; v < bcc.vertex_num(); ++v) {
                if (int vid = art_id[v]; vid < 0) {
                    ++_vertex_num[_comp_id[v]];
                } else {
                    _vertex_num[vid] = 1;
                    for (int cid : _g[vid]) ++_vertex_num[cid];
                }
            }
        }

        int size() const { return _edge_comp_num + _isolated_vertex_num + _art_num; }
        
        bool is_articulation_point(int id)    const { return id >= _edge_comp_num + _isolated_vertex_num; }
        bool is_biconnected_component(int id) const { return not is_articulation_point(id); }
        bool is_isolated_vertex(int id)       const { return id >= _edge_comp_num and is_biconnected_component(id); }

        const std::vector<int>& operator[](int id) const { return _g[id]; }
        std::vector<int>& operator[](int id) { return _g[id]; }

        int vertex_num(int id) const { return _vertex_num[id]; }

        int component_id(int vertex) const {
            return _comp_id[vertex];
        }

    private:
        int _edge_comp_num;
        int _isolated_vertex_num;
        int _art_num;
        int _node_num;
        std::vector<std::vector<int>> _g;
        std::vector<int> _vertex_num;
        std::vector<int> _comp_id;
    };
} // namespace suisen
Back to top page