C++ Library for Competitive Programming
#include "emthrm/graph/eulerian_trail_in_directed_graph.hpp"
グラフのすべての辺を一度だけ通る路である。
閉路でないオイラー路が存在するグラフである。
連結グラフ $G$ が準オイラーグラフである必要十分条件は
オイラー閉路 (Euler circuit) が存在するグラフである。
連結グラフ $G$ がオイラーグラフである必要十分条件は
$O(\lvert V \rvert + \lvert E \rvert)$
名前 | 戻り値 |
---|---|
template <typename CostType> std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(std::vector<std::vector<Edge<CostType>>> graph, int s = -1);
|
有向グラフ $\mathrm{graph}$ における始点 $s$ のオイラー路。ただし存在しないときは空配列を返す。 |
struct EulerianTrailInUndirectedGraph;
名前 | 説明 |
---|---|
std::vector<int> trail |
オイラー路。ただし存在しないときは空配列となる。 |
名前 | 効果・戻り値 |
---|---|
explicit EulerianTrailInUndirectedGraph(const int n); |
頂点数 $N$ の無向グラフのオブジェクトを構築する。 |
void add_edge(const int u, const int v); |
辺 $(u, v)$ を加える。 |
bool build(int s = -1); |
始点 $s$ のオイラー路を構築できたか。 |
オイラー路 有向グラフ版
オイラー路 無向グラフ版
#ifndef EMTHRM_GRAPH_EULERIAN_TRAIL_IN_DIRECTED_GRAPH_HPP_
#define EMTHRM_GRAPH_EULERIAN_TRAIL_IN_DIRECTED_GRAPH_HPP_
#include <algorithm>
#include <iterator>
#include <ranges>
#include <utility>
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template <typename CostType>
std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(
std::vector<std::vector<Edge<CostType>>> graph, int s = -1) {
const int n = graph.size();
int edge_num = 0;
std::vector<int> deg(n, 0);
for (int i = 0; i < n; ++i) {
edge_num += graph[i].size();
deg[i] += graph[i].size();
for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
--deg[e];
}
}
if (edge_num == 0) [[unlikely]] return {};
const int not0 = n - std::count(deg.begin(), deg.end(), 0);
if (not0 == 0) {
if (s == -1) {
s = std::distance(
graph.begin(),
std::find_if_not(
graph.begin(), graph.end(),
[](const std::vector<Edge<CostType>>& edges) -> bool {
return edges.empty();
}));
}
} else if (not0 == 2) {
bool t_exists = false;
for (int i = 0; i < n; ++i) {
if (deg[i] == 0) continue;
if (deg[i] == 1) {
if (s == -1) s = i;
if (s != i) return {};
} else if (deg[i] == -1) {
if (t_exists) return {};
t_exists = true;
} else {
return {};
}
}
} else {
return {};
}
std::vector<Edge<CostType>> res;
const auto dfs = [&graph, &res](auto dfs, const int ver) -> void {
while (!graph[ver].empty()) {
const Edge<CostType> e = graph[ver].back();
graph[ver].pop_back();
dfs(dfs, e.dst);
res.emplace_back(e);
}
};
dfs(dfs, s);
if (std::cmp_equal(res.size(), edge_num)) {
std::reverse(res.begin(), res.end());
return res;
}
return {};
}
} // namespace emthrm
#endif // EMTHRM_GRAPH_EULERIAN_TRAIL_IN_DIRECTED_GRAPH_HPP_
#line 1 "include/emthrm/graph/eulerian_trail_in_directed_graph.hpp"
#include <algorithm>
#include <iterator>
#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 11 "include/emthrm/graph/eulerian_trail_in_directed_graph.hpp"
namespace emthrm {
template <typename CostType>
std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(
std::vector<std::vector<Edge<CostType>>> graph, int s = -1) {
const int n = graph.size();
int edge_num = 0;
std::vector<int> deg(n, 0);
for (int i = 0; i < n; ++i) {
edge_num += graph[i].size();
deg[i] += graph[i].size();
for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
--deg[e];
}
}
if (edge_num == 0) [[unlikely]] return {};
const int not0 = n - std::count(deg.begin(), deg.end(), 0);
if (not0 == 0) {
if (s == -1) {
s = std::distance(
graph.begin(),
std::find_if_not(
graph.begin(), graph.end(),
[](const std::vector<Edge<CostType>>& edges) -> bool {
return edges.empty();
}));
}
} else if (not0 == 2) {
bool t_exists = false;
for (int i = 0; i < n; ++i) {
if (deg[i] == 0) continue;
if (deg[i] == 1) {
if (s == -1) s = i;
if (s != i) return {};
} else if (deg[i] == -1) {
if (t_exists) return {};
t_exists = true;
} else {
return {};
}
}
} else {
return {};
}
std::vector<Edge<CostType>> res;
const auto dfs = [&graph, &res](auto dfs, const int ver) -> void {
while (!graph[ver].empty()) {
const Edge<CostType> e = graph[ver].back();
graph[ver].pop_back();
dfs(dfs, e.dst);
res.emplace_back(e);
}
};
dfs(dfs, s);
if (std::cmp_equal(res.size(), edge_num)) {
std::reverse(res.begin(), res.end());
return res;
}
return {};
}
} // namespace emthrm