C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
#include "emthrm/graph/2-edge-connected_components_by_imos.hpp"
無向グラフを橋の存在しない部分グラフに分解することである。
それぞれの成分には、任意の3点を始点・経由点・終点とする辺素パスが存在し、さらに任意の2点を結ぶ2本以上の辺素パスが存在する。
二重辺連結成分を一つの頂点に縮約することで得られる木である。
template <typename CostType, bool IS_FULL_VER = false> struct TwoEdgeConnectedComponents : Lowlink<CostType>;
CostType
IS_FULL_VER
std::vector<int> id
id[i]
std::vector<std::vector<int>> vertices
vertices[i]
std::vector<std::vector<Edge<CostType>>> g
explicit TwoEdgeConnectedComponents(const std::vector<std::vector<Edge<CostType>>>& graph);
template <typename CostType, bool IS_FULL_VER = false> struct TwoEdgeConnectedComponentsByImos;
std::vector<Edge<CostType>> bridge
explicit TwoEdgeConnectedComponentsByImos(const std::vector<std::vector<Edge<CostType>>>& graph);
lowlink 版
#ifndef EMTHRM_GRAPH_2_EDGE_CONNECTED_COMPONENTS_BY_IMOS_HPP_ #define EMTHRM_GRAPH_2_EDGE_CONNECTED_COMPONENTS_BY_IMOS_HPP_ #include <algorithm> #include <set> #include <queue> #include <ranges> #include <utility> #include <vector> #include "emthrm/graph/edge.hpp" #include "emthrm/graph/enumerate_bridges.hpp" namespace emthrm { template <typename CostType, bool IS_FULL_VER = false> struct TwoEdgeConnectedComponentsByImos { std::vector<int> id; std::vector<Edge<CostType>> bridge; std::vector<std::vector<int>> vertices; std::vector<std::vector<Edge<CostType>>> g; explicit TwoEdgeConnectedComponentsByImos( const std::vector<std::vector<Edge<CostType>>>& graph) : bridge(enumerate_bridges(graph)) { const int n = graph.size(); id.assign(n, -1); std::set<std::pair<int, int>> st; for (const Edge<CostType>& e : bridge) st.emplace(e.src, e.dst); int m = 0; std::queue<int> que; for (int i = 0; i < n; ++i) { if (id[i] != -1) continue; que.emplace(i); id[i] = m++; if constexpr (IS_FULL_VER) vertices.emplace_back(std::vector<int>{i}); while (!que.empty()) { const int ver = que.front(); que.pop(); for (const int e : graph[ver] | std::views::transform(&Edge<CostType>::dst)) { if (id[e] == -1 && !st.contains(std::minmax(ver, e))) { id[e] = id[i]; if constexpr (IS_FULL_VER) vertices.back().emplace_back(e); que.emplace(e); } } } } g.resize(m); for (const Edge<CostType>& e : bridge) { const int u = id[e.src], v = id[e.dst]; g[u].emplace_back(u, v, e.cost); g[v].emplace_back(v, u, e.cost); } if constexpr (IS_FULL_VER) { for (int i = 0; i < m; ++i) { std::sort(vertices[i].begin(), vertices[i].end()); } } } }; } // namespace emthrm #endif // EMTHRM_GRAPH_2_EDGE_CONNECTED_COMPONENTS_BY_IMOS_HPP_
#line 1 "include/emthrm/graph/2-edge-connected_components_by_imos.hpp" #include <algorithm> #include <set> #include <queue> #include <ranges> #include <utility> #include <vector> #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/enumerate_bridges.hpp" #line 6 "include/emthrm/graph/enumerate_bridges.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 8 "include/emthrm/graph/enumerate_bridges.hpp" namespace emthrm { template <typename CostType> std::vector<Edge<CostType>> enumerate_bridges( const std::vector<std::vector<Edge<CostType>>>& graph) { const int n = graph.size(); std::vector<Edge<CostType>> res; std::vector<int> depth(n, -1), imos(n, 0); const auto dfs = [&graph, &res, &depth, &imos]( auto dfs, const int par, const int ver) -> void { bool has_multiple_edges = false; for (const Edge<CostType>& e : graph[ver]) { if (depth[e.dst] == -1) { depth[e.dst] = depth[ver] + 1; dfs(dfs, ver, e.dst); if (imos[e.dst] == 0) { res.emplace_back(std::min(ver, e.dst), std::max(ver, e.dst), e.cost); } imos[ver] += imos[e.dst]; } else if (!has_multiple_edges && e.dst == par) { has_multiple_edges = true; } else if (depth[e.dst] < depth[ver]) { ++imos[ver]; --imos[e.dst]; } } }; for (int i = 0; i < n; ++i) { if (depth[i] == -1) { depth[i] = 0; dfs(dfs, -1, i); } } return res; } } // namespace emthrm #line 13 "include/emthrm/graph/2-edge-connected_components_by_imos.hpp" namespace emthrm { template <typename CostType, bool IS_FULL_VER = false> struct TwoEdgeConnectedComponentsByImos { std::vector<int> id; std::vector<Edge<CostType>> bridge; std::vector<std::vector<int>> vertices; std::vector<std::vector<Edge<CostType>>> g; explicit TwoEdgeConnectedComponentsByImos( const std::vector<std::vector<Edge<CostType>>>& graph) : bridge(enumerate_bridges(graph)) { const int n = graph.size(); id.assign(n, -1); std::set<std::pair<int, int>> st; for (const Edge<CostType>& e : bridge) st.emplace(e.src, e.dst); int m = 0; std::queue<int> que; for (int i = 0; i < n; ++i) { if (id[i] != -1) continue; que.emplace(i); id[i] = m++; if constexpr (IS_FULL_VER) vertices.emplace_back(std::vector<int>{i}); while (!que.empty()) { const int ver = que.front(); que.pop(); for (const int e : graph[ver] | std::views::transform(&Edge<CostType>::dst)) { if (id[e] == -1 && !st.contains(std::minmax(ver, e))) { id[e] = id[i]; if constexpr (IS_FULL_VER) vertices.back().emplace_back(e); que.emplace(e); } } } } g.resize(m); for (const Edge<CostType>& e : bridge) { const int u = id[e.src], v = id[e.dst]; g[u].emplace_back(u, v, e.cost); g[v].emplace_back(v, u, e.cost); } if constexpr (IS_FULL_VER) { for (int i = 0; i < m; ++i) { std::sort(vertices[i].begin(), vertices[i].end()); } } } }; } // namespace emthrm