eulerian_trail.hpp¶
判断有向/无向多重图是否存在欧拉迹或欧拉回路，并构造一条合法路径。
Complexity: Time: O(V + E). Space: O(V + E).
AC 记录：eulerian_trail_directed, eulerian_trail_undirected。
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 {
/// @brief Vertex sequence and input edge ids of an Eulerian trail.
struct eulerian_trail_result {
std::vector<int> vs;
std::vector<int> eid;
};
/// @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>> &es,
int s = -1) {
assert(n >= 0);
assert(-1 <= s && s < n);
std::vector<std::vector<int>> g(n);
std::vector<int> deg(n), dou(n);
for (int ei1 = 0; ei1 < int(es.size()); ei1++) {
auto [u, v] = es[ei1];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].push_back(ei1);
dou[u]++;
deg[v]++;
}
if (es.empty()) {
eulerian_trail_result res;
if (n > 0) {
res.vs.push_back(s == -1 ? 0 : s);
}
return res;
}
int st = -1;
int en = -1;
for (int x = 0; x < n; x++) {
int dif = dou[x] - deg[x];
if (dif == 1) {
if (st != -1) {
return std::nullopt;
}
st = x;
} else if (dif == -1) {
if (en != -1) {
return std::nullopt;
}
en = x;
} else if (dif != 0) {
return std::nullopt;
}
}
if ((st == -1) != (en == -1)) {
return std::nullopt;
}
if (s != -1) {
if ((st != -1 && s != st) || (st == -1 && dou[s] == 0)) {
return std::nullopt;
}
} else if (st != -1) {
s = st;
} else {
s = int(
std::find_if(dou.begin(), dou.end(), [](int de1) { return de1 > 0; }) -
dou.begin());
}
std::vector<int> off(n);
std::vector<int> vs1 = {s};
std::vector<int> es1;
eulerian_trail_result res;
while (!vs1.empty()) {
int x = vs1.back();
if (off[x] < int(g[x].size())) {
int ei1 = g[x][off[x]++];
vs1.push_back(es[ei1].second);
es1.push_back(ei1);
} else {
res.vs.push_back(x);
vs1.pop_back();
if (!es1.empty()) {
res.eid.push_back(es1.back());
es1.pop_back();
}
}
}
if (res.eid.size() != es.size()) {
return std::nullopt;
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.eid.begin(), res.eid.end());
return res;
}
/// @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>> &es,
int s = -1) {
assert(n >= 0);
assert(-1 <= s && s < n);
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> de1(n);
for (int ei1 = 0; ei1 < int(es.size()); ei1++) {
auto [u, v] = es[ei1];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, ei1);
g[v].emplace_back(u, ei1);
de1[u]++;
de1[v]++;
}
if (es.empty()) {
eulerian_trail_result res;
if (n > 0) {
res.vs.push_back(s == -1 ? 0 : s);
}
return res;
}
std::vector<int> odd;
for (int x = 0; x < n; x++) {
if (de1[x] & 1) {
odd.push_back(x);
}
}
if (!odd.empty() && odd.size() != 2) {
return std::nullopt;
}
if (s != -1) {
if ((!odd.empty() && s != odd[0] && s != odd[1]) ||
(odd.empty() && de1[s] == 0)) {
return std::nullopt;
}
} else if (!odd.empty()) {
s = odd[0];
} else {
s = int(
std::find_if(de1.begin(), de1.end(), [](int val) { return val > 0; }) -
de1.begin());
}
std::vector<int> off(n);
std::vector<bool> vis(es.size());
std::vector<int> vs1 = {s};
std::vector<int> es1;
eulerian_trail_result res;
while (!vs1.empty()) {
int x = vs1.back();
while (off[x] < int(g[x].size()) && vis[g[x][off[x]].second]) {
off[x]++;
}
if (off[x] < int(g[x].size())) {
auto [nxt, ei1] = g[x][off[x]++];
vis[ei1] = true;
vs1.push_back(nxt);
es1.push_back(ei1);
} else {
res.vs.push_back(x);
vs1.pop_back();
if (!es1.empty()) {
res.eid.push_back(es1.back());
es1.pop_back();
}
}
}
if (res.eid.size() != es.size()) {
return std::nullopt;
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.eid.begin(), res.eid.end());
return res;
}
} // namespace noya
#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> vs;
std::vector<int> eid;
};
/// @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>> &es,
int s = -1) {
assert(n >= 0);
assert(-1 <= s && s < n);
std::vector<std::vector<int>> g(n);
std::vector<int> deg(n), dou(n);
for (int ei1 = 0; ei1 < int(es.size()); ei1++) {
auto [u, v] = es[ei1];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].push_back(ei1);
dou[u]++;
deg[v]++;
}
if (es.empty()) {
eulerian_trail_result res;
if (n > 0) {
res.vs.push_back(s == -1 ? 0 : s);
}
return res;
}
int st = -1;
int en = -1;
for (int x = 0; x < n; x++) {
int dif = dou[x] - deg[x];
if (dif == 1) {
if (st != -1) {
return std::nullopt;
}
st = x;
} else if (dif == -1) {
if (en != -1) {
return std::nullopt;
}
en = x;
} else if (dif != 0) {
return std::nullopt;
}
}
if ((st == -1) != (en == -1)) {
return std::nullopt;
}
if (s != -1) {
if ((st != -1 && s != st) || (st == -1 && dou[s] == 0)) {
return std::nullopt;
}
} else if (st != -1) {
s = st;
} else {
s = int(
std::find_if(dou.begin(), dou.end(), [](int de1) { return de1 > 0; }) -
dou.begin());
}
std::vector<int> off(n);
std::vector<int> vs1 = {s};
std::vector<int> es1;
eulerian_trail_result res;
while (!vs1.empty()) {
int x = vs1.back();
if (off[x] < int(g[x].size())) {
int ei1 = g[x][off[x]++];
vs1.push_back(es[ei1].second);
es1.push_back(ei1);
} else {
res.vs.push_back(x);
vs1.pop_back();
if (!es1.empty()) {
res.eid.push_back(es1.back());
es1.pop_back();
}
}
}
if (res.eid.size() != es.size()) {
return std::nullopt;
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.eid.begin(), res.eid.end());
return res;
}
/// @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>> &es,
int s = -1) {
assert(n >= 0);
assert(-1 <= s && s < n);
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> de1(n);
for (int ei1 = 0; ei1 < int(es.size()); ei1++) {
auto [u, v] = es[ei1];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, ei1);
g[v].emplace_back(u, ei1);
de1[u]++;
de1[v]++;
}
if (es.empty()) {
eulerian_trail_result res;
if (n > 0) {
res.vs.push_back(s == -1 ? 0 : s);
}
return res;
}
std::vector<int> odd;
for (int x = 0; x < n; x++) {
if (de1[x] & 1) {
odd.push_back(x);
}
}
if (!odd.empty() && odd.size() != 2) {
return std::nullopt;
}
if (s != -1) {
if ((!odd.empty() && s != odd[0] && s != odd[1]) ||
(odd.empty() && de1[s] == 0)) {
return std::nullopt;
}
} else if (!odd.empty()) {
s = odd[0];
} else {
s = int(
std::find_if(de1.begin(), de1.end(), [](int val) { return val > 0; }) -
de1.begin());
}
std::vector<int> off(n);
std::vector<bool> vis(es.size());
std::vector<int> vs1 = {s};
std::vector<int> es1;
eulerian_trail_result res;
while (!vs1.empty()) {
int x = vs1.back();
while (off[x] < int(g[x].size()) && vis[g[x][off[x]].second]) {
off[x]++;
}
if (off[x] < int(g[x].size())) {
auto [nxt, ei1] = g[x][off[x]++];
vis[ei1] = true;
vs1.push_back(nxt);
es1.push_back(ei1);
} else {
res.vs.push_back(x);
vs1.pop_back();
if (!es1.empty()) {
res.eid.push_back(es1.back());
es1.pop_back();
}
}
}
if (res.eid.size() != es.size()) {
return std::nullopt;
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.eid.begin(), res.eid.end());
return res;
}
} // 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> vs;
std::vector<int> eid;
};
/// @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>> &es,
int s = -1) {
assert(n >= 0);
assert(-1 <= s && s < n);
std::vector<std::vector<int>> g(n);
std::vector<int> deg(n), dou(n);
for (int ei1 = 0; ei1 < int(es.size()); ei1++) {
auto [u, v] = es[ei1];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].push_back(ei1);
dou[u]++;
deg[v]++;
}
if (es.empty()) {
eulerian_trail_result res;
if (n > 0) {
res.vs.push_back(s == -1 ? 0 : s);
}
return res;
}
int st = -1;
int en = -1;
for (int x = 0; x < n; x++) {
int dif = dou[x] - deg[x];
if (dif == 1) {
if (st != -1) {
return std::nullopt;
}
st = x;
} else if (dif == -1) {
if (en != -1) {
return std::nullopt;
}
en = x;
} else if (dif != 0) {
return std::nullopt;
}
}
if ((st == -1) != (en == -1)) {
return std::nullopt;
}
if (s != -1) {
if ((st != -1 && s != st) || (st == -1 && dou[s] == 0)) {
return std::nullopt;
}
} else if (st != -1) {
s = st;
} else {
s = int(
std::find_if(dou.begin(), dou.end(), [](int de1) { return de1 > 0; }) -
dou.begin());
}
std::vector<int> off(n);
std::vector<int> vs1 = {s};
std::vector<int> es1;
eulerian_trail_result res;
while (!vs1.empty()) {
int x = vs1.back();
if (off[x] < int(g[x].size())) {
int ei1 = g[x][off[x]++];
vs1.push_back(es[ei1].second);
es1.push_back(ei1);
} else {
res.vs.push_back(x);
vs1.pop_back();
if (!es1.empty()) {
res.eid.push_back(es1.back());
es1.pop_back();
}
}
}
if (res.eid.size() != es.size()) {
return std::nullopt;
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.eid.begin(), res.eid.end());
return res;
}
/// @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>> &es,
int s = -1) {
assert(n >= 0);
assert(-1 <= s && s < n);
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<int> de1(n);
for (int ei1 = 0; ei1 < int(es.size()); ei1++) {
auto [u, v] = es[ei1];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
g[u].emplace_back(v, ei1);
g[v].emplace_back(u, ei1);
de1[u]++;
de1[v]++;
}
if (es.empty()) {
eulerian_trail_result res;
if (n > 0) {
res.vs.push_back(s == -1 ? 0 : s);
}
return res;
}
std::vector<int> odd;
for (int x = 0; x < n; x++) {
if (de1[x] & 1) {
odd.push_back(x);
}
}
if (!odd.empty() && odd.size() != 2) {
return std::nullopt;
}
if (s != -1) {
if ((!odd.empty() && s != odd[0] && s != odd[1]) ||
(odd.empty() && de1[s] == 0)) {
return std::nullopt;
}
} else if (!odd.empty()) {
s = odd[0];
} else {
s = int(
std::find_if(de1.begin(), de1.end(), [](int val) { return val > 0; }) -
de1.begin());
}
std::vector<int> off(n);
std::vector<bool> vis(es.size());
std::vector<int> vs1 = {s};
std::vector<int> es1;
eulerian_trail_result res;
while (!vs1.empty()) {
int x = vs1.back();
while (off[x] < int(g[x].size()) && vis[g[x][off[x]].second]) {
off[x]++;
}
if (off[x] < int(g[x].size())) {
auto [nxt, ei1] = g[x][off[x]++];
vis[ei1] = true;
vs1.push_back(nxt);
es1.push_back(ei1);
} else {
res.vs.push_back(x);
vs1.pop_back();
if (!es1.empty()) {
res.eid.push_back(es1.back());
es1.pop_back();
}
}
}
if (res.eid.size() != es.size()) {
return std::nullopt;
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.eid.begin(), res.eid.end());
return res;
}
} // namespace noya