euler_walk.hpp¶
Find an Euler trail in an undirected multigraph, or nullopt if none exists.
在图中构造恰好经过每条边一次的欧拉游走，并返回顶点与边顺序。
Implementation¶
#ifndef NOYA_EULER_WALK_HPP
#define NOYA_EULER_WALK_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
struct euler_walk_result {
std::vector<int> vertices;
std::vector<int> edge_ids;
};
namespace euler_walk_internal {
inline euler_walk_result
hierholzer(const std::vector<std::vector<std::pair<int, int>>> &graph,
int edge_count, int start) {
std::vector<int> next_edge(graph.size());
std::vector<bool> used(edge_count);
std::vector<std::pair<int, int>> stack = {{start, -1}};
euler_walk_result reversed;
while (!stack.empty()) {
int u = stack.back().first;
while (next_edge[u] < int(graph[u].size()) &&
used[graph[u][next_edge[u]].second]) {
next_edge[u]++;
}
if (next_edge[u] == int(graph[u].size())) {
auto [vertex, incoming_edge] = stack.back();
stack.pop_back();
reversed.vertices.push_back(vertex);
if (incoming_edge != -1) {
reversed.edge_ids.push_back(incoming_edge);
}
continue;
}
auto [v, edge_id] = graph[u][next_edge[u]++];
if (!used[edge_id]) {
used[edge_id] = true;
stack.emplace_back(v, edge_id);
}
}
std::reverse(reversed.vertices.begin(), reversed.vertices.end());
std::reverse(reversed.edge_ids.begin(), reversed.edge_ids.end());
return reversed;
}
} // namespace euler_walk_internal
/// @brief Find an Euler trail in an undirected multigraph, or nullopt if none
/// exists.
inline std::optional<euler_walk_result>
euler_walk_undirected(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
if (n == 0) {
return edges.empty() && start == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (start < -1 || start >= n) {
return std::nullopt;
}
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> degree(n);
for (int id = 0; id < int(edges.size()); id++) {
auto [u, v] = edges[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, id);
graph[v].emplace_back(u, id);
degree[u]++;
degree[v]++;
}
std::vector<int> odd;
for (int u = 0; u < n; u++) {
if (degree[u] & 1) {
odd.push_back(u);
}
}
if (odd.size() != 0 && odd.size() != 2) {
return std::nullopt;
}
if (edges.empty()) {
int chosen = start == -1 ? 0 : start;
return euler_walk_result{{chosen}, {}};
}
if (start == -1) {
start = odd.empty()
? int(std::find_if(degree.begin(), degree.end(),
[](int value) { return value > 0; }) -
degree.begin())
: odd[0];
} else if ((!odd.empty() && degree[start] % 2 == 0) || degree[start] == 0) {
return std::nullopt;
}
euler_walk_result result =
euler_walk_internal::hierholzer(graph, int(edges.size()), start);
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
return result;
}
/// @brief Find an Euler trail in a directed multigraph, or nullopt if none
/// exists.
inline std::optional<euler_walk_result>
euler_walk_directed(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
if (n == 0) {
return edges.empty() && start == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (start < -1 || start >= n) {
return std::nullopt;
}
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> in_degree(n), out_degree(n);
for (int id = 0; id < int(edges.size()); id++) {
auto [u, v] = edges[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, id);
out_degree[u]++;
in_degree[v]++;
}
int required_start = -1;
int required_end = -1;
for (int u = 0; u < n; u++) {
int difference = out_degree[u] - in_degree[u];
if (difference == 1 && required_start == -1) {
required_start = u;
} else if (difference == -1 && required_end == -1) {
required_end = u;
} else if (difference != 0) {
return std::nullopt;
}
}
if ((required_start == -1) != (required_end == -1)) {
return std::nullopt;
}
if (edges.empty()) {
int chosen = start == -1 ? 0 : start;
return euler_walk_result{{chosen}, {}};
}
if (start == -1) {
start = required_start;
if (start == -1) {
start = int(std::find_if(out_degree.begin(), out_degree.end(),
[](int value) { return value > 0; }) -
out_degree.begin());
}
} else if ((required_start != -1 && start != required_start) ||
out_degree[start] == 0) {
return std::nullopt;
}
euler_walk_result result =
euler_walk_internal::hierholzer(graph, int(edges.size()), start);
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
return result;
}
} // namespace noya
#endif // NOYA_EULER_WALK_HPP
#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: O(V + E).
/// Space: O(V + E).
namespace noya {
struct euler_walk_result {
std::vector<int> vertices;
std::vector<int> edge_ids;
};
namespace euler_walk_internal {
inline euler_walk_result
hierholzer(const std::vector<std::vector<std::pair<int, int>>> &graph,
int edge_count, int start) {
std::vector<int> next_edge(graph.size());
std::vector<bool> used(edge_count);
std::vector<std::pair<int, int>> stack = {{start, -1}};
euler_walk_result reversed;
while (!stack.empty()) {
int u = stack.back().first;
while (next_edge[u] < int(graph[u].size()) &&
used[graph[u][next_edge[u]].second]) {
next_edge[u]++;
}
if (next_edge[u] == int(graph[u].size())) {
auto [vertex, incoming_edge] = stack.back();
stack.pop_back();
reversed.vertices.push_back(vertex);
if (incoming_edge != -1) {
reversed.edge_ids.push_back(incoming_edge);
}
continue;
}
auto [v, edge_id] = graph[u][next_edge[u]++];
if (!used[edge_id]) {
used[edge_id] = true;
stack.emplace_back(v, edge_id);
}
}
std::reverse(reversed.vertices.begin(), reversed.vertices.end());
std::reverse(reversed.edge_ids.begin(), reversed.edge_ids.end());
return reversed;
}
} // namespace euler_walk_internal
/// @brief Find an Euler trail in an undirected multigraph, or nullopt if none
/// exists.
inline std::optional<euler_walk_result>
euler_walk_undirected(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
if (n == 0) {
return edges.empty() && start == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (start < -1 || start >= n) {
return std::nullopt;
}
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> degree(n);
for (int id = 0; id < int(edges.size()); id++) {
auto [u, v] = edges[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, id);
graph[v].emplace_back(u, id);
degree[u]++;
degree[v]++;
}
std::vector<int> odd;
for (int u = 0; u < n; u++) {
if (degree[u] & 1) {
odd.push_back(u);
}
}
if (odd.size() != 0 && odd.size() != 2) {
return std::nullopt;
}
if (edges.empty()) {
int chosen = start == -1 ? 0 : start;
return euler_walk_result{{chosen}, {}};
}
if (start == -1) {
start = odd.empty()
? int(std::find_if(degree.begin(), degree.end(),
[](int value) { return value > 0; }) -
degree.begin())
: odd[0];
} else if ((!odd.empty() && degree[start] % 2 == 0) || degree[start] == 0) {
return std::nullopt;
}
euler_walk_result result =
euler_walk_internal::hierholzer(graph, int(edges.size()), start);
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
return result;
}
/// @brief Find an Euler trail in a directed multigraph, or nullopt if none
/// exists.
inline std::optional<euler_walk_result>
euler_walk_directed(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
if (n == 0) {
return edges.empty() && start == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (start < -1 || start >= n) {
return std::nullopt;
}
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> in_degree(n), out_degree(n);
for (int id = 0; id < int(edges.size()); id++) {
auto [u, v] = edges[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, id);
out_degree[u]++;
in_degree[v]++;
}
int required_start = -1;
int required_end = -1;
for (int u = 0; u < n; u++) {
int difference = out_degree[u] - in_degree[u];
if (difference == 1 && required_start == -1) {
required_start = u;
} else if (difference == -1 && required_end == -1) {
required_end = u;
} else if (difference != 0) {
return std::nullopt;
}
}
if ((required_start == -1) != (required_end == -1)) {
return std::nullopt;
}
if (edges.empty()) {
int chosen = start == -1 ? 0 : start;
return euler_walk_result{{chosen}, {}};
}
if (start == -1) {
start = required_start;
if (start == -1) {
start = int(std::find_if(out_degree.begin(), out_degree.end(),
[](int value) { return value > 0; }) -
out_degree.begin());
}
} else if ((required_start != -1 && start != required_start) ||
out_degree[start] == 0) {
return std::nullopt;
}
euler_walk_result result =
euler_walk_internal::hierholzer(graph, int(edges.size()), start);
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
return result;
}
} // namespace noya