eulerian_trail.hpp¶
Vertex sequence and input edge ids of an Eulerian trail.
Verified by eulerian_trail_directed, eulerian_trail_undirected.
判断有向/无向多重图是否存在欧拉迹或欧拉回路，并构造一条合法路径。
Implementation¶
#ifndef NOYA_EULERIAN_TRAIL_HPP
#define NOYA_EULERIAN_TRAIL_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Vertex sequence and input edge ids of an Eulerian trail.
struct eulerian_trail_result {
std::vector<int> vertices;
std::vector<int> edge_ids;
};
/// @brief Construct a directed Eulerian trail using every input edge once, or
/// return nullopt when none exists. Set start to -1 to choose it automatically.
inline std::optional<eulerian_trail_result>
directed_eulerian_trail(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
assert(-1 <= start && start < n);
std::vector<std::vector<int>> graph(n);
std::vector<int> indegree(n), outdegree(n);
for (int edge_id = 0; edge_id < int(edges.size()); edge_id++) {
auto [u, v] = edges[edge_id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].push_back(edge_id);
outdegree[u]++;
indegree[v]++;
}
if (edges.empty()) {
eulerian_trail_result result;
if (n > 0) {
result.vertices.push_back(start == -1 ? 0 : start);
}
return result;
}
int required_start = -1;
int required_end = -1;
for (int vertex = 0; vertex < n; vertex++) {
int difference = outdegree[vertex] - indegree[vertex];
if (difference == 1) {
if (required_start != -1) {
return std::nullopt;
}
required_start = vertex;
} else if (difference == -1) {
if (required_end != -1) {
return std::nullopt;
}
required_end = vertex;
} else if (difference != 0) {
return std::nullopt;
}
}
if ((required_start == -1) != (required_end == -1)) {
return std::nullopt;
}
if (start != -1) {
if ((required_start != -1 && start != required_start) ||
(required_start == -1 && outdegree[start] == 0)) {
return std::nullopt;
}
} else if (required_start != -1) {
start = required_start;
} else {
start = int(std::find_if(outdegree.begin(), outdegree.end(),
[](int degree) { return degree > 0; }) -
outdegree.begin());
}
std::vector<int> offset(n);
std::vector<int> vertex_stack = {start};
std::vector<int> edge_stack;
eulerian_trail_result result;
while (!vertex_stack.empty()) {
int vertex = vertex_stack.back();
if (offset[vertex] < int(graph[vertex].size())) {
int edge_id = graph[vertex][offset[vertex]++];
vertex_stack.push_back(edges[edge_id].second);
edge_stack.push_back(edge_id);
} else {
result.vertices.push_back(vertex);
vertex_stack.pop_back();
if (!edge_stack.empty()) {
result.edge_ids.push_back(edge_stack.back());
edge_stack.pop_back();
}
}
}
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
std::reverse(result.vertices.begin(), result.vertices.end());
std::reverse(result.edge_ids.begin(), result.edge_ids.end());
return result;
}
/// @brief Construct an undirected Eulerian trail using every input edge once,
/// or return nullopt when none exists. Parallel edges and self-loops are
/// supported; set start to -1 to choose it automatically.
inline std::optional<eulerian_trail_result>
undirected_eulerian_trail(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
assert(-1 <= start && start < n);
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> degree(n);
for (int edge_id = 0; edge_id < int(edges.size()); edge_id++) {
auto [u, v] = edges[edge_id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, edge_id);
graph[v].emplace_back(u, edge_id);
degree[u]++;
degree[v]++;
}
if (edges.empty()) {
eulerian_trail_result result;
if (n > 0) {
result.vertices.push_back(start == -1 ? 0 : start);
}
return result;
}
std::vector<int> odd_vertices;
for (int vertex = 0; vertex < n; vertex++) {
if (degree[vertex] & 1) {
odd_vertices.push_back(vertex);
}
}
if (!odd_vertices.empty() && odd_vertices.size() != 2) {
return std::nullopt;
}
if (start != -1) {
if ((!odd_vertices.empty() && start != odd_vertices[0] &&
start != odd_vertices[1]) ||
(odd_vertices.empty() && degree[start] == 0)) {
return std::nullopt;
}
} else if (!odd_vertices.empty()) {
start = odd_vertices[0];
} else {
start = int(std::find_if(degree.begin(), degree.end(),
[](int value) { return value > 0; }) -
degree.begin());
}
std::vector<int> offset(n);
std::vector<bool> used(edges.size());
std::vector<int> vertex_stack = {start};
std::vector<int> edge_stack;
eulerian_trail_result result;
while (!vertex_stack.empty()) {
int vertex = vertex_stack.back();
while (offset[vertex] < int(graph[vertex].size()) &&
used[graph[vertex][offset[vertex]].second]) {
offset[vertex]++;
}
if (offset[vertex] < int(graph[vertex].size())) {
auto [next, edge_id] = graph[vertex][offset[vertex]++];
used[edge_id] = true;
vertex_stack.push_back(next);
edge_stack.push_back(edge_id);
} else {
result.vertices.push_back(vertex);
vertex_stack.pop_back();
if (!edge_stack.empty()) {
result.edge_ids.push_back(edge_stack.back());
edge_stack.pop_back();
}
}
}
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
std::reverse(result.vertices.begin(), result.vertices.end());
std::reverse(result.edge_ids.begin(), result.edge_ids.end());
return result;
}
} // namespace noya
#endif // NOYA_EULERIAN_TRAIL_HPP
#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: O(V + E).
/// Space: O(V + E).
namespace noya {
/// @brief Vertex sequence and input edge ids of an Eulerian trail.
struct eulerian_trail_result {
std::vector<int> vertices;
std::vector<int> edge_ids;
};
/// @brief Construct a directed Eulerian trail using every input edge once, or
/// return nullopt when none exists. Set start to -1 to choose it automatically.
inline std::optional<eulerian_trail_result>
directed_eulerian_trail(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
assert(-1 <= start && start < n);
std::vector<std::vector<int>> graph(n);
std::vector<int> indegree(n), outdegree(n);
for (int edge_id = 0; edge_id < int(edges.size()); edge_id++) {
auto [u, v] = edges[edge_id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].push_back(edge_id);
outdegree[u]++;
indegree[v]++;
}
if (edges.empty()) {
eulerian_trail_result result;
if (n > 0) {
result.vertices.push_back(start == -1 ? 0 : start);
}
return result;
}
int required_start = -1;
int required_end = -1;
for (int vertex = 0; vertex < n; vertex++) {
int difference = outdegree[vertex] - indegree[vertex];
if (difference == 1) {
if (required_start != -1) {
return std::nullopt;
}
required_start = vertex;
} else if (difference == -1) {
if (required_end != -1) {
return std::nullopt;
}
required_end = vertex;
} else if (difference != 0) {
return std::nullopt;
}
}
if ((required_start == -1) != (required_end == -1)) {
return std::nullopt;
}
if (start != -1) {
if ((required_start != -1 && start != required_start) ||
(required_start == -1 && outdegree[start] == 0)) {
return std::nullopt;
}
} else if (required_start != -1) {
start = required_start;
} else {
start = int(std::find_if(outdegree.begin(), outdegree.end(),
[](int degree) { return degree > 0; }) -
outdegree.begin());
}
std::vector<int> offset(n);
std::vector<int> vertex_stack = {start};
std::vector<int> edge_stack;
eulerian_trail_result result;
while (!vertex_stack.empty()) {
int vertex = vertex_stack.back();
if (offset[vertex] < int(graph[vertex].size())) {
int edge_id = graph[vertex][offset[vertex]++];
vertex_stack.push_back(edges[edge_id].second);
edge_stack.push_back(edge_id);
} else {
result.vertices.push_back(vertex);
vertex_stack.pop_back();
if (!edge_stack.empty()) {
result.edge_ids.push_back(edge_stack.back());
edge_stack.pop_back();
}
}
}
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
std::reverse(result.vertices.begin(), result.vertices.end());
std::reverse(result.edge_ids.begin(), result.edge_ids.end());
return result;
}
/// @brief Construct an undirected Eulerian trail using every input edge once,
/// or return nullopt when none exists. Parallel edges and self-loops are
/// supported; set start to -1 to choose it automatically.
inline std::optional<eulerian_trail_result>
undirected_eulerian_trail(int n, const std::vector<std::pair<int, int>> &edges,
int start = -1) {
assert(n >= 0);
assert(-1 <= start && start < n);
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> degree(n);
for (int edge_id = 0; edge_id < int(edges.size()); edge_id++) {
auto [u, v] = edges[edge_id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, edge_id);
graph[v].emplace_back(u, edge_id);
degree[u]++;
degree[v]++;
}
if (edges.empty()) {
eulerian_trail_result result;
if (n > 0) {
result.vertices.push_back(start == -1 ? 0 : start);
}
return result;
}
std::vector<int> odd_vertices;
for (int vertex = 0; vertex < n; vertex++) {
if (degree[vertex] & 1) {
odd_vertices.push_back(vertex);
}
}
if (!odd_vertices.empty() && odd_vertices.size() != 2) {
return std::nullopt;
}
if (start != -1) {
if ((!odd_vertices.empty() && start != odd_vertices[0] &&
start != odd_vertices[1]) ||
(odd_vertices.empty() && degree[start] == 0)) {
return std::nullopt;
}
} else if (!odd_vertices.empty()) {
start = odd_vertices[0];
} else {
start = int(std::find_if(degree.begin(), degree.end(),
[](int value) { return value > 0; }) -
degree.begin());
}
std::vector<int> offset(n);
std::vector<bool> used(edges.size());
std::vector<int> vertex_stack = {start};
std::vector<int> edge_stack;
eulerian_trail_result result;
while (!vertex_stack.empty()) {
int vertex = vertex_stack.back();
while (offset[vertex] < int(graph[vertex].size()) &&
used[graph[vertex][offset[vertex]].second]) {
offset[vertex]++;
}
if (offset[vertex] < int(graph[vertex].size())) {
auto [next, edge_id] = graph[vertex][offset[vertex]++];
used[edge_id] = true;
vertex_stack.push_back(next);
edge_stack.push_back(edge_id);
} else {
result.vertices.push_back(vertex);
vertex_stack.pop_back();
if (!edge_stack.empty()) {
result.edge_ids.push_back(edge_stack.back());
edge_stack.pop_back();
}
}
}
if (result.edge_ids.size() != edges.size()) {
return std::nullopt;
}
std::reverse(result.vertices.begin(), result.vertices.end());
std::reverse(result.edge_ids.begin(), result.edge_ids.end());
return result;
}
} // namespace noya