This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/graph/two_edge_connected_components.hpp"
多重辺があったり、非連結でも動きます。
#ifndef SUISEN_TWO_EDGE_CONNECTED_COMPONENTS #define SUISEN_TWO_EDGE_CONNECTED_COMPONENTS #include "library/graph/low_link.hpp" namespace suisen { struct TwoEdgeConnectedComponents : public LowLink { TwoEdgeConnectedComponents() : TwoEdgeConnectedComponents(0) {} TwoEdgeConnectedComponents(const int n) : LowLink(n), _comp_id(_n, -1), _comp_num(0) {} TwoEdgeConnectedComponents(const int n, const std::vector<std::pair<int, int>> &edges) : LowLink(n, edges), _comp_id(_n, -1), _comp_num(0) { dfs_for_all_connected_components(); } void build() { LowLink::build(); dfs_for_all_connected_components(); } int component_num() const { assert(_built); return _comp_num; } int operator[](int v) const { assert(_built); return _comp_id[v]; } std::vector<std::vector<int>> groups() const { assert(_built); std::vector<std::vector<int>> res(component_num()); for (int i = 0; i < _n; ++i) res[_comp_id[i]].push_back(i); return res; } // v -> list of (adjacent_vertex, edge_id) std::vector<std::vector<std::pair<int, int>>> reduced_forest() const { assert(_built); std::vector<std::vector<std::pair<int, int>>> reduced(_comp_num); for (int u = 0; u < _n; ++u) { for (const auto &[v, edge_id] : _g[u]) { const int comp_u = (*this)[u], comp_v = (*this)[v]; if (comp_u != comp_v) reduced[comp_u].emplace_back(comp_v, edge_id); } } return reduced; } private: std::vector<int> _comp_id; int _comp_num; void dfs(int u, int p) { if (p >= 0 and _low_link[u] <= _pre_order[p]) { _comp_id[u] = _comp_id[p]; } else { _comp_id[u] = _comp_num++; } for (const auto &e : _g[u]) { const int v = e.first; if (_comp_id[v] < 0) dfs(v, u); } } void dfs_for_all_connected_components() { _comp_num = 0; for (int i = 0; i < _n; ++i) { if (_comp_id[i] < 0) dfs(i, -1); } } }; } // namespace suisen #endif // SUISEN_TWO_EDGE_CONNECTED_COMPONENTS
#line 1 "library/graph/two_edge_connected_components.hpp" #line 1 "library/graph/low_link.hpp" #include <cassert> #include <cstddef> #include <cstdint> #include <utility> #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 5 "library/graph/two_edge_connected_components.hpp" namespace suisen { struct TwoEdgeConnectedComponents : public LowLink { TwoEdgeConnectedComponents() : TwoEdgeConnectedComponents(0) {} TwoEdgeConnectedComponents(const int n) : LowLink(n), _comp_id(_n, -1), _comp_num(0) {} TwoEdgeConnectedComponents(const int n, const std::vector<std::pair<int, int>> &edges) : LowLink(n, edges), _comp_id(_n, -1), _comp_num(0) { dfs_for_all_connected_components(); } void build() { LowLink::build(); dfs_for_all_connected_components(); } int component_num() const { assert(_built); return _comp_num; } int operator[](int v) const { assert(_built); return _comp_id[v]; } std::vector<std::vector<int>> groups() const { assert(_built); std::vector<std::vector<int>> res(component_num()); for (int i = 0; i < _n; ++i) res[_comp_id[i]].push_back(i); return res; } // v -> list of (adjacent_vertex, edge_id) std::vector<std::vector<std::pair<int, int>>> reduced_forest() const { assert(_built); std::vector<std::vector<std::pair<int, int>>> reduced(_comp_num); for (int u = 0; u < _n; ++u) { for (const auto &[v, edge_id] : _g[u]) { const int comp_u = (*this)[u], comp_v = (*this)[v]; if (comp_u != comp_v) reduced[comp_u].emplace_back(comp_v, edge_id); } } return reduced; } private: std::vector<int> _comp_id; int _comp_num; void dfs(int u, int p) { if (p >= 0 and _low_link[u] <= _pre_order[p]) { _comp_id[u] = _comp_id[p]; } else { _comp_id[u] = _comp_num++; } for (const auto &e : _g[u]) { const int v = e.first; if (_comp_id[v] < 0) dfs(v, u); } } void dfs_for_all_connected_components() { _comp_num = 0; for (int i = 0; i < _n; ++i) { if (_comp_id[i] < 0) dfs(i, -1); } } }; } // namespace suisen