euler_walk.hpp¶
在图中构造恰好经过每条边一次的欧拉游走，并返回顶点与边顺序。
Complexity: Time: O(V + E). Space: O(V + E).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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> vs;
std::vector<int> eid;
};
namespace euler_walk_internal {
inline euler_walk_result
hierholzer(const std::vector<std::vector<std::pair<int, int>>> &g, int m,
int s) {
std::vector<int> ptr(g.size());
std::vector<bool> vis(m);
std::vector<std::pair<int, int>> stk = {{s, -1}};
euler_walk_result rev;
while (!stk.empty()) {
int u = stk.back().first;
while (ptr[u] < int(g[u].size()) && vis[g[u][ptr[u]].second]) {
ptr[u]++;
}
if (ptr[u] == int(g[u].size())) {
auto [u1, ie] = stk.back();
stk.pop_back();
rev.vs.push_back(u1);
if (ie != -1) {
rev.eid.push_back(ie);
}
continue;
}
auto [v, ei1] = g[u][ptr[u]++];
if (!vis[ei1]) {
vis[ei1] = true;
stk.emplace_back(v, ei1);
}
}
std::reverse(rev.vs.begin(), rev.vs.end());
std::reverse(rev.eid.begin(), rev.eid.end());
return rev;
}
} // 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>> &es,
int s = -1) {
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;
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> deg(n);
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, id);
g[v].emplace_back(u, id);
deg[u]++;
deg[v]++;
}
std::vector<int> odd;
for (int u = 0; u < n; u++) {
if (deg[u] & 1) {
odd.push_back(u);
}
}
if (odd.size() != 0 && odd.size() != 2) {
return std::nullopt;
}
if (es.empty()) {
int sel = s == -1 ? 0 : s;
return euler_walk_result{{sel}, {}};
}
if (s == -1) {
s = odd.empty() ? int(std::find_if(deg.begin(), deg.end(),
[](int val) { return val > 0; }) -
deg.begin())
: odd[0];
} else if ((!odd.empty() && deg[s] % 2 == 0) || deg[s] == 0) {
return std::nullopt;
}
euler_walk_result res = euler_walk_internal::hierholzer(g, int(es.size()), s);
if (res.eid.size() != es.size()) {
return std::nullopt;
}
return res;
}
/// @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>> &es,
int s = -1) {
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;
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> din(n), dou(n);
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, id);
dou[u]++;
din[v]++;
}
int st = -1;
int en = -1;
for (int u = 0; u < n; u++) {
int dif = dou[u] - din[u];
if (dif == 1 && st == -1) {
st = u;
} else if (dif == -1 && en == -1) {
en = u;
} else if (dif != 0) {
return std::nullopt;
}
}
if ((st == -1) != (en == -1)) {
return std::nullopt;
}
if (es.empty()) {
int sel = s == -1 ? 0 : s;
return euler_walk_result{{sel}, {}};
}
if (s == -1) {
s = st;
if (s == -1) {
s = int(std::find_if(dou.begin(), dou.end(),
[](int val) { return val > 0; }) -
dou.begin());
}
} else if ((st != -1 && s != st) || dou[s] == 0) {
return std::nullopt;
}
euler_walk_result res = euler_walk_internal::hierholzer(g, int(es.size()), s);
if (res.eid.size() != es.size()) {
return std::nullopt;
}
return res;
}
} // namespace noya
#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> vs;
std::vector<int> eid;
};
namespace euler_walk_internal {
inline euler_walk_result
hierholzer(const std::vector<std::vector<std::pair<int, int>>> &g, int m,
int s) {
std::vector<int> ptr(g.size());
std::vector<bool> vis(m);
std::vector<std::pair<int, int>> stk = {{s, -1}};
euler_walk_result rev;
while (!stk.empty()) {
int u = stk.back().first;
while (ptr[u] < int(g[u].size()) && vis[g[u][ptr[u]].second]) {
ptr[u]++;
}
if (ptr[u] == int(g[u].size())) {
auto [u1, ie] = stk.back();
stk.pop_back();
rev.vs.push_back(u1);
if (ie != -1) {
rev.eid.push_back(ie);
}
continue;
}
auto [v, ei1] = g[u][ptr[u]++];
if (!vis[ei1]) {
vis[ei1] = true;
stk.emplace_back(v, ei1);
}
}
std::reverse(rev.vs.begin(), rev.vs.end());
std::reverse(rev.eid.begin(), rev.eid.end());
return rev;
}
} // 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>> &es,
int s = -1) {
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;
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> deg(n);
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, id);
g[v].emplace_back(u, id);
deg[u]++;
deg[v]++;
}
std::vector<int> odd;
for (int u = 0; u < n; u++) {
if (deg[u] & 1) {
odd.push_back(u);
}
}
if (odd.size() != 0 && odd.size() != 2) {
return std::nullopt;
}
if (es.empty()) {
int sel = s == -1 ? 0 : s;
return euler_walk_result{{sel}, {}};
}
if (s == -1) {
s = odd.empty() ? int(std::find_if(deg.begin(), deg.end(),
[](int val) { return val > 0; }) -
deg.begin())
: odd[0];
} else if ((!odd.empty() && deg[s] % 2 == 0) || deg[s] == 0) {
return std::nullopt;
}
euler_walk_result res = euler_walk_internal::hierholzer(g, int(es.size()), s);
if (res.eid.size() != es.size()) {
return std::nullopt;
}
return res;
}
/// @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>> &es,
int s = -1) {
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;
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> din(n), dou(n);
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, id);
dou[u]++;
din[v]++;
}
int st = -1;
int en = -1;
for (int u = 0; u < n; u++) {
int dif = dou[u] - din[u];
if (dif == 1 && st == -1) {
st = u;
} else if (dif == -1 && en == -1) {
en = u;
} else if (dif != 0) {
return std::nullopt;
}
}
if ((st == -1) != (en == -1)) {
return std::nullopt;
}
if (es.empty()) {
int sel = s == -1 ? 0 : s;
return euler_walk_result{{sel}, {}};
}
if (s == -1) {
s = st;
if (s == -1) {
s = int(std::find_if(dou.begin(), dou.end(),
[](int val) { return val > 0; }) -
dou.begin());
}
} else if ((st != -1 && s != st) || dou[s] == 0) {
return std::nullopt;
}
euler_walk_result res = euler_walk_internal::hierholzer(g, int(es.size()), s);
if (res.eid.size() != es.size()) {
return std::nullopt;
}
return res;
}
} // 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> vs;
std::vector<int> eid;
};
namespace euler_walk_internal {
inline euler_walk_result
hierholzer(const std::vector<std::vector<std::pair<int, int>>> &g, int m,
int s) {
std::vector<int> ptr(g.size());
std::vector<bool> vis(m);
std::vector<std::pair<int, int>> stk = {{s, -1}};
euler_walk_result rev;
while (!stk.empty()) {
int u = stk.back().first;
while (ptr[u] < int(g[u].size()) && vis[g[u][ptr[u]].second]) {
ptr[u]++;
}
if (ptr[u] == int(g[u].size())) {
auto [u1, ie] = stk.back();
stk.pop_back();
rev.vs.push_back(u1);
if (ie != -1) {
rev.eid.push_back(ie);
}
continue;
}
auto [v, ei1] = g[u][ptr[u]++];
if (!vis[ei1]) {
vis[ei1] = true;
stk.emplace_back(v, ei1);
}
}
std::reverse(rev.vs.begin(), rev.vs.end());
std::reverse(rev.eid.begin(), rev.eid.end());
return rev;
}
} // 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>> &es,
int s = -1) {
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;
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> deg(n);
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, id);
g[v].emplace_back(u, id);
deg[u]++;
deg[v]++;
}
std::vector<int> odd;
for (int u = 0; u < n; u++) {
if (deg[u] & 1) {
odd.push_back(u);
}
}
if (odd.size() != 0 && odd.size() != 2) {
return std::nullopt;
}
if (es.empty()) {
int sel = s == -1 ? 0 : s;
return euler_walk_result{{sel}, {}};
}
if (s == -1) {
s = odd.empty() ? int(std::find_if(deg.begin(), deg.end(),
[](int val) { return val > 0; }) -
deg.begin())
: odd[0];
} else if ((!odd.empty() && deg[s] % 2 == 0) || deg[s] == 0) {
return std::nullopt;
}
euler_walk_result res = euler_walk_internal::hierholzer(g, int(es.size()), s);
if (res.eid.size() != es.size()) {
return std::nullopt;
}
return res;
}
/// @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>> &es,
int s = -1) {
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;
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> din(n), dou(n);
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, id);
dou[u]++;
din[v]++;
}
int st = -1;
int en = -1;
for (int u = 0; u < n; u++) {
int dif = dou[u] - din[u];
if (dif == 1 && st == -1) {
st = u;
} else if (dif == -1 && en == -1) {
en = u;
} else if (dif != 0) {
return std::nullopt;
}
}
if ((st == -1) != (en == -1)) {
return std::nullopt;
}
if (es.empty()) {
int sel = s == -1 ? 0 : s;
return euler_walk_result{{sel}, {}};
}
if (s == -1) {
s = st;
if (s == -1) {
s = int(std::find_if(dou.begin(), dou.end(),
[](int val) { return val > 0; }) -
dou.begin());
}
} else if ((st != -1 && s != st) || dou[s] == 0) {
return std::nullopt;
}
euler_walk_result res = euler_walk_internal::hierholzer(g, int(es.size()), s);
if (res.eid.size() != es.size()) {
return std::nullopt;
}
return res;
}
} // namespace noya