cp-library
C++ Library for Competitive Programming
辺
(include/emthrm/graph/edge.hpp)
- View this file on GitHub
- Last update: 2023-02-24 21:17:22+09:00
- Include:
#include "emthrm/graph/edge.hpp"
Required by
二重辺連結成分 (2-edge-connected component) 分解 いもす法版
(include/emthrm/graph/2-edge-connected_components_by_imos.hpp)
- 二重辺連結成分 (2-edge-connected component) 分解 lowlink 版
(include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp)
- 二重頂点連結成分 (biconnected component) 分解
(include/emthrm/graph/biconnected_component.hpp)
- 彩色数 (chromatic number)
(include/emthrm/graph/chromatic_number.hpp)
- 補グラフの連結成分分解
(include/emthrm/graph/connencted_component_of_complement_graph.hpp)
- 有向閉路 (directed cycle) の検出
(include/emthrm/graph/detect_directed_cycle.hpp)
- 道 (path) の検出
(include/emthrm/graph/detect_path.hpp)
- 橋の検出
(include/emthrm/graph/enumerate_bridges.hpp)
- オイラー路 (Eulerian trail) 有向グラフ版
(include/emthrm/graph/eulerian_trail_in_directed_graph.hpp)
- 内周 (girth) 有向グラフ版
(include/emthrm/graph/girth_in_directed_graph.hpp)
- 内周 (girth) 無向グラフ版
(include/emthrm/graph/girth_in_undirected_graph.hpp)
- 二部グラフ (bipartite graph) 判定
(include/emthrm/graph/is_bipartite.hpp)
- Kruskal 法
(include/emthrm/graph/kruskal.hpp)
- lowlink
(include/emthrm/graph/lowlink.hpp)
- 行列木定理 (Kirchhoff's matrix tree theorem)
(include/emthrm/graph/matrix_tree_theorem.hpp)
- 区間に辺を張るテク
(include/emthrm/graph/noshi_graph.hpp)
- Prim 法
(include/emthrm/graph/prim.hpp)
- 有向非巡回グラフ上の到達可能性判定
(include/emthrm/graph/reachability_on_dag.hpp)
- Bellman–Ford 法
(include/emthrm/graph/shortest_path/bellman-ford.hpp)
- Dijkstra 法
(include/emthrm/graph/shortest_path/dijkstra.hpp)
- 強連結成分 (strongly connected components) 分解
(include/emthrm/graph/strongly_connected_components.hpp)
- トポロジカルソート (topological sort)
(include/emthrm/graph/topological_sort.hpp)
- 巡回セールスマン問題 (traveling salesman problem)
(include/emthrm/graph/traveling_salesman_problem.hpp)
- 重心 (centroid)
(include/emthrm/graph/tree/centroid.hpp)
- 重心分解 (centroid decompositon)
(include/emthrm/graph/tree/centroid_decomposition.hpp)
- double sweep
(include/emthrm/graph/tree/double_sweep.hpp)
- Euler tour technique
(include/emthrm/graph/tree/euler_tour_technique.hpp)
- heavy-light decomposition
(include/emthrm/graph/tree/heavy-light_decomposition.hpp)
- 最小共通祖先 (lowest common ancestor) ダブリング版
(include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp)
- 最小共通祖先 (lowest common ancestor) Euler tour technique 版
(include/emthrm/graph/tree/lowest_common_ancestor_by_euler_tour_technique.hpp)
- 全方位木 DP
(include/emthrm/graph/tree/rerooting_dp.hpp)
- unicyclic graph / 1-tree
(include/emthrm/graph/unicyclic_graph.hpp)
Verified with
- グラフ/二重辺連結成分分解 いもす法版
(test/graph/2-edge-connected_components_by_imos.test.cpp)
グラフ/二重辺連結成分分解 lowlink 版
(test/graph/2-edge-connected_components_by_lowlink.test.cpp)
- グラフ/二重頂点連結成分分解
(test/graph/biconnected_component.test.cpp)
- グラフ/彩色数
(test/graph/chromatic_number.test.cpp)
- グラフ/補グラフの連結成分分解
(test/graph/connencted_component_of_complement_graph.test.cpp)
- グラフ/有向閉路の検出
(test/graph/detect_directed_cycle.test.cpp)
- グラフ/道の検出
(test/graph/detect_path.test.cpp)
- グラフ/橋の列挙
(test/graph/enumerate_bridges.test.cpp)
- グラフ/オイラー路 有向グラフ版
(test/graph/eulerian_trail_in_directed_graph.test.cpp)
- グラフ/フロー/最小費用流/最小流量制約付き最小費用流
(test/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.test.cpp)
- グラフ/内周
(test/graph/girth.test.cpp)
- グラフ/二部グラフ判定
(test/graph/is_bipartite.test.cpp)
- グラフ/Kruskal 法
(test/graph/kruskal.test.cpp)
- グラフ/lowlink（橋）
(test/graph/lowlink.1.test.cpp)
- グラフ/lowlink（関節点）
(test/graph/lowlink.2.test.cpp)
- グラフ/行列木定理
(test/graph/matrix_tree_theorem.test.cpp)
- グラフ/区間に辺を張るテク
(test/graph/noshi_graph.test.cpp)
- グラフ/Prim 法
(test/graph/prim.test.cpp)
- グラフ/有向非巡回グラフ上の到達可能性判定
(test/graph/reachability_on_dag.test.cpp)
- グラフ/最短路問題/Bellman–Ford 法
(test/graph/shortest_path/bellman-ford.test.cpp)
- グラフ/最短路問題/Dijkstra 法
(test/graph/shortest_path/dijkstra.test.cpp)
- グラフ/強連結成分分解
(test/graph/strongly_connected_components.test.cpp)
- グラフ/トポロジカルソート
(test/graph/topological_sort.test.cpp)
- グラフ/巡回セールスマン問題
(test/graph/traveling_salesman_problem.test.cpp)
- グラフ/木/重心
(test/graph/tree/centroid.test.cpp)
- グラフ/木/重心分解
(test/graph/tree/centroid_decomposition.test.cpp)
- グラフ/木/double sweep
(test/graph/tree/double_sweep.test.cpp)
- グラフ/木/heavy-light decomposition
(test/graph/tree/heavy-light_decomposition.1.test.cpp)
- グラフ/木/heavy-light decomposition（最小共通祖先）
(test/graph/tree/heavy-light_decomposition.2.test.cpp)
- グラフ/木/最小共通祖先 ダブリング版
(test/graph/tree/lowest_common_ancestor_by_doubling.test.cpp)
- グラフ/木/最小共通祖先 Euler tour technique 版
(test/graph/tree/lowest_common_ancestor_by_euler_tour.test.cpp)
- グラフ/木/全方位木 DP
(test/graph/tree/rerooting_dp.test.cpp)
- グラフ/unicyclic graph
(test/graph/unicyclic_graph.test.cpp)
- 数学/基底
(test/math/basis.test.cpp)
- 数学/行列/連立一次方程式
(test/math/matrix/linear_equation.test.cpp)
Code
/**
* @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/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_