euler_walk.hpp¶
用连续邻接表和结果数组内的遍历栈构造有向/无向欧拉迹，返回顶点与输入边编号；支持自环、重边与指定起点。
Complexity: Time: \(O(V + E)\). Space: \(O(V + E)\), including the result. Empty-edge inputs take \(O(1)\) time and space.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E). Space: O(V + E), including the result.
/// Empty-edge inputs take O(1) time and space.
#include <cassert>
#include <cstddef>
#include <limits>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
struct euler_walk_result {
std::vector<int> vs;
std::vector<int> eid;
};
namespace euler_walk_internal {
template <bool Directed>
std::optional<euler_walk_result>
solve(int n, const std::vector<std::pair<int, int>> &es, int s) {
assert(n >= 0);
if (n == 0) {
return es.empty() && s == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (s < -1 || s >= n) {
return std::nullopt;
}
if (es.empty()) {
return euler_walk_result{{s == -1 ? 0 : s}, {}};
}
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<std::size_t> off(std::size_t(n) + 1);
int first = -1, start = -1, end = -1, odd = 0;
{
std::vector<int> balance(Directed ? n : 0);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++off[u];
if constexpr (Directed) {
++balance[u];
--balance[v];
} else {
++off[v];
}
}
for (int u = 0; u < n; ++u) {
if (off[u] && first == -1) {
first = u;
}
if constexpr (Directed) {
if (balance[u] == 1 && start == -1) {
start = u;
} else if (balance[u] == -1 && end == -1) {
end = u;
} else if (balance[u] != 0) {
return std::nullopt;
}
} else if (off[u] & 1) {
if (++odd > 2) {
return std::nullopt;
}
if (start == -1) {
start = u;
}
}
}
if constexpr (Directed) {
if ((start == -1) != (end == -1) ||
(s != -1 && ((start != -1 && s != start) || off[s] == 0))) {
return std::nullopt;
}
} else if ((odd != 0 && odd != 2) ||
(s != -1 && ((odd && !(off[s] & 1)) || off[s] == 0))) {
return std::nullopt;
}
}
if (s == -1) {
s = start == -1 ? first : start;
}
// Counts become end offsets. Reverse filling turns them into start offsets
// and preserves the input edge order in every adjacency row.
for (int u = 0; u < n; ++u) {
off[u + 1] += off[u];
}
std::vector<std::pair<int, int>> adj(off[n]);
for (int id = m; id-- > 0;) {
auto [u, v] = es[id];
adj[--off[u]] = {v, id};
if constexpr (!Directed) {
adj[--off[v]] = {u, id};
}
}
std::vector<std::size_t> ptr(off.begin(), off.end() - 1);
std::vector<char> used(Directed ? 0 : m);
euler_walk_result res;
res.vs.resize(es.size() + 1);
res.eid.resize(es.size());
// The prefix is the DFS stack; the suffix is the finished forward answer.
// write-top equals the number of unused edges, so the regions never clash.
std::size_t top = 0, write = es.size();
res.vs[0] = s;
for (;;) {
assert(top <= write);
int u = res.vs[top];
if constexpr (!Directed) {
while (ptr[u] < off[u + 1] && used[adj[ptr[u]].second]) {
++ptr[u];
}
}
if (ptr[u] < off[u + 1]) {
auto [v, id] = adj[ptr[u]++];
if constexpr (!Directed) {
used[id] = true;
}
assert(top < write);
res.eid[top] = id;
res.vs[++top] = v;
} else {
res.vs[write] = u;
if (top == 0) {
break;
}
res.eid[write - 1] = res.eid[top - 1];
--top;
--write;
}
}
if (write != 0) {
return std::nullopt; // Some edges lie outside the visited component.
}
return res;
}
} // namespace euler_walk_internal
/// @brief Find an Euler trail in an undirected multigraph, or nullopt if none
/// exists from the requested start. Self-loops and parallel edges are allowed.
/// Require n>=0, valid endpoints, and an int-representable edge count.
/// s=-1 chooses the smallest odd vertex, or the smallest nonisolated vertex
/// for a circuit. Other invalid starts return nullopt. Inputs are unchanged;
/// adjacency choices follow input order, preserving the original exact trail.
/// With no edges, return {s} (default 0), or empty vectors when n=0 and s=-1.
inline std::optional<euler_walk_result>
euler_walk_undirected(int n, const std::vector<std::pair<int, int>> &es,
int s = -1) {
return euler_walk_internal::solve<false>(n, es, s);
}
/// @brief Directed counterpart, with the same empty/start conventions.
/// s=-1 selects the unique out-in=1 vertex for an open trail, otherwise the
/// smallest vertex with an outgoing edge. Each edge has only one adjacency
/// entry, so no visited-edge array is needed in the directed specialization.
inline std::optional<euler_walk_result>
euler_walk_directed(int n, const std::vector<std::pair<int, int>> &es,
int s = -1) {
return euler_walk_internal::solve<true>(n, es, s);
}
} // namespace noya
// NOYA_EULER_WALK_HPP
#ifndef NOYA_EULER_WALK_HPP
#define NOYA_EULER_WALK_HPP 1
/// @complexity Time: O(V + E). Space: O(V + E), including the result.
/// Empty-edge inputs take O(1) time and space.
#include <cassert>
#include <cstddef>
#include <limits>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
struct euler_walk_result {
std::vector<int> vs;
std::vector<int> eid;
};
namespace euler_walk_internal {
template <bool Directed>
std::optional<euler_walk_result>
solve(int n, const std::vector<std::pair<int, int>> &es, int s) {
assert(n >= 0);
if (n == 0) {
return es.empty() && s == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (s < -1 || s >= n) {
return std::nullopt;
}
if (es.empty()) {
return euler_walk_result{{s == -1 ? 0 : s}, {}};
}
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<std::size_t> off(std::size_t(n) + 1);
int first = -1, start = -1, end = -1, odd = 0;
{
std::vector<int> balance(Directed ? n : 0);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++off[u];
if constexpr (Directed) {
++balance[u];
--balance[v];
} else {
++off[v];
}
}
for (int u = 0; u < n; ++u) {
if (off[u] && first == -1) {
first = u;
}
if constexpr (Directed) {
if (balance[u] == 1 && start == -1) {
start = u;
} else if (balance[u] == -1 && end == -1) {
end = u;
} else if (balance[u] != 0) {
return std::nullopt;
}
} else if (off[u] & 1) {
if (++odd > 2) {
return std::nullopt;
}
if (start == -1) {
start = u;
}
}
}
if constexpr (Directed) {
if ((start == -1) != (end == -1) ||
(s != -1 && ((start != -1 && s != start) || off[s] == 0))) {
return std::nullopt;
}
} else if ((odd != 0 && odd != 2) ||
(s != -1 && ((odd && !(off[s] & 1)) || off[s] == 0))) {
return std::nullopt;
}
}
if (s == -1) {
s = start == -1 ? first : start;
}
// Counts become end offsets. Reverse filling turns them into start offsets
// and preserves the input edge order in every adjacency row.
for (int u = 0; u < n; ++u) {
off[u + 1] += off[u];
}
std::vector<std::pair<int, int>> adj(off[n]);
for (int id = m; id-- > 0;) {
auto [u, v] = es[id];
adj[--off[u]] = {v, id};
if constexpr (!Directed) {
adj[--off[v]] = {u, id};
}
}
std::vector<std::size_t> ptr(off.begin(), off.end() - 1);
std::vector<char> used(Directed ? 0 : m);
euler_walk_result res;
res.vs.resize(es.size() + 1);
res.eid.resize(es.size());
// The prefix is the DFS stack; the suffix is the finished forward answer.
// write-top equals the number of unused edges, so the regions never clash.
std::size_t top = 0, write = es.size();
res.vs[0] = s;
for (;;) {
assert(top <= write);
int u = res.vs[top];
if constexpr (!Directed) {
while (ptr[u] < off[u + 1] && used[adj[ptr[u]].second]) {
++ptr[u];
}
}
if (ptr[u] < off[u + 1]) {
auto [v, id] = adj[ptr[u]++];
if constexpr (!Directed) {
used[id] = true;
}
assert(top < write);
res.eid[top] = id;
res.vs[++top] = v;
} else {
res.vs[write] = u;
if (top == 0) {
break;
}
res.eid[write - 1] = res.eid[top - 1];
--top;
--write;
}
}
if (write != 0) {
return std::nullopt; // Some edges lie outside the visited component.
}
return res;
}
} // namespace euler_walk_internal
/// @brief Find an Euler trail in an undirected multigraph, or nullopt if none
/// exists from the requested start. Self-loops and parallel edges are allowed.
/// Require n>=0, valid endpoints, and an int-representable edge count.
/// s=-1 chooses the smallest odd vertex, or the smallest nonisolated vertex
/// for a circuit. Other invalid starts return nullopt. Inputs are unchanged;
/// adjacency choices follow input order, preserving the original exact trail.
/// With no edges, return {s} (default 0), or empty vectors when n=0 and s=-1.
inline std::optional<euler_walk_result>
euler_walk_undirected(int n, const std::vector<std::pair<int, int>> &es,
int s = -1) {
return euler_walk_internal::solve<false>(n, es, s);
}
/// @brief Directed counterpart, with the same empty/start conventions.
/// s=-1 selects the unique out-in=1 vertex for an open trail, otherwise the
/// smallest vertex with an outgoing edge. Each edge has only one adjacency
/// entry, so no visited-edge array is needed in the directed specialization.
inline std::optional<euler_walk_result>
euler_walk_directed(int n, const std::vector<std::pair<int, int>> &es,
int s = -1) {
return euler_walk_internal::solve<true>(n, es, s);
}
} // namespace noya
#endif // NOYA_EULER_WALK_HPP
/// @complexity Time: O(V + E). Space: O(V + E), including the result.
/// Empty-edge inputs take O(1) time and space.
#include <cassert>
#include <cstddef>
#include <limits>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
struct euler_walk_result {
std::vector<int> vs;
std::vector<int> eid;
};
namespace euler_walk_internal {
template <bool Directed>
std::optional<euler_walk_result>
solve(int n, const std::vector<std::pair<int, int>> &es, int s) {
assert(n >= 0);
if (n == 0) {
return es.empty() && s == -1
? std::optional<euler_walk_result>(euler_walk_result{})
: std::nullopt;
}
if (s < -1 || s >= n) {
return std::nullopt;
}
if (es.empty()) {
return euler_walk_result{{s == -1 ? 0 : s}, {}};
}
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<std::size_t> off(std::size_t(n) + 1);
int first = -1, start = -1, end = -1, odd = 0;
{
std::vector<int> balance(Directed ? n : 0);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++off[u];
if constexpr (Directed) {
++balance[u];
--balance[v];
} else {
++off[v];
}
}
for (int u = 0; u < n; ++u) {
if (off[u] && first == -1) {
first = u;
}
if constexpr (Directed) {
if (balance[u] == 1 && start == -1) {
start = u;
} else if (balance[u] == -1 && end == -1) {
end = u;
} else if (balance[u] != 0) {
return std::nullopt;
}
} else if (off[u] & 1) {
if (++odd > 2) {
return std::nullopt;
}
if (start == -1) {
start = u;
}
}
}
if constexpr (Directed) {
if ((start == -1) != (end == -1) ||
(s != -1 && ((start != -1 && s != start) || off[s] == 0))) {
return std::nullopt;
}
} else if ((odd != 0 && odd != 2) ||
(s != -1 && ((odd && !(off[s] & 1)) || off[s] == 0))) {
return std::nullopt;
}
}
if (s == -1) {
s = start == -1 ? first : start;
}
// Counts become end offsets. Reverse filling turns them into start offsets
// and preserves the input edge order in every adjacency row.
for (int u = 0; u < n; ++u) {
off[u + 1] += off[u];
}
std::vector<std::pair<int, int>> adj(off[n]);
for (int id = m; id-- > 0;) {
auto [u, v] = es[id];
adj[--off[u]] = {v, id};
if constexpr (!Directed) {
adj[--off[v]] = {u, id};
}
}
std::vector<std::size_t> ptr(off.begin(), off.end() - 1);
std::vector<char> used(Directed ? 0 : m);
euler_walk_result res;
res.vs.resize(es.size() + 1);
res.eid.resize(es.size());
// The prefix is the DFS stack; the suffix is the finished forward answer.
// write-top equals the number of unused edges, so the regions never clash.
std::size_t top = 0, write = es.size();
res.vs[0] = s;
for (;;) {
assert(top <= write);
int u = res.vs[top];
if constexpr (!Directed) {
while (ptr[u] < off[u + 1] && used[adj[ptr[u]].second]) {
++ptr[u];
}
}
if (ptr[u] < off[u + 1]) {
auto [v, id] = adj[ptr[u]++];
if constexpr (!Directed) {
used[id] = true;
}
assert(top < write);
res.eid[top] = id;
res.vs[++top] = v;
} else {
res.vs[write] = u;
if (top == 0) {
break;
}
res.eid[write - 1] = res.eid[top - 1];
--top;
--write;
}
}
if (write != 0) {
return std::nullopt; // Some edges lie outside the visited component.
}
return res;
}
} // namespace euler_walk_internal
/// @brief Find an Euler trail in an undirected multigraph, or nullopt if none
/// exists from the requested start. Self-loops and parallel edges are allowed.
/// Require n>=0, valid endpoints, and an int-representable edge count.
/// s=-1 chooses the smallest odd vertex, or the smallest nonisolated vertex
/// for a circuit. Other invalid starts return nullopt. Inputs are unchanged;
/// adjacency choices follow input order, preserving the original exact trail.
/// With no edges, return {s} (default 0), or empty vectors when n=0 and s=-1.
inline std::optional<euler_walk_result>
euler_walk_undirected(int n, const std::vector<std::pair<int, int>> &es,
int s = -1) {
return euler_walk_internal::solve<false>(n, es, s);
}
/// @brief Directed counterpart, with the same empty/start conventions.
/// s=-1 selects the unique out-in=1 vertex for an open trail, otherwise the
/// smallest vertex with an outgoing edge. Each edge has only one adjacency
/// entry, so no visited-edge array is needed in the directed specialization.
inline std::optional<euler_walk_result>
euler_walk_directed(int n, const std::vector<std::pair<int, int>> &es,
int s = -1) {
return euler_walk_internal::solve<true>(n, es, s);
}
} // namespace noya
// NOYA_EULER_WALK_HPP