This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/graph/block_cut_forest.hpp"
#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