graph/EulerWalk.h

• View this file on GitHub
• Last update: 2025-11-20 20:30:36+07:00

Verified with

• tests/Eulerian_Trail_Directed.test.cpp
• tests/Eulerian_Trail_Undirected.test.cpp

Code

pair<vi, vi> EulerWalk(int n, vector<vector<pii>>& adj, int m, bool dir, bool cyc) {
  vi D(n), ptr(n), used(m), nodes, edges;
  vector<pii> st;
  int src = 0, bad = 0;
  for (int i = 0; i < n; ++i) {
    if (dir) for (auto& p : adj[i]) D[i]++, D[p.first]--;
    else D[i] = sz(adj[i]) & 1;
  }
  for (int i = 0; i < n; ++i) {
    if (sz(adj[i]) && adj[src].empty()) src = i;
    if (D[i]) {
      bad++;
      if ((dir && D[i] > 0) || (!dir)) src = i;
    }
  }
  if (bad > 2 || (cyc && bad) || (dir && bad && D[src] != 1)) return {};
  st.pb({src, -1});
  while (!st.empty()) {
    int u = st.back().first;
    if (ptr[u] < sz(adj[u])) {
      auto [v, id] = adj[u][ptr[u]++];
      if (!used[id]) used[id] = 1, st.pb({v, id});
    } else {
      auto [v, id] = st.back();
      st.pop_back();
      nodes.pb(v);
      if (id != -1) edges.pb(id);
    }
  }
  if (sz(edges) != m) return {};
  reverse(all(nodes)), reverse(all(edges));
  return {nodes, edges};
}

#line 1 "graph/EulerWalk.h"
pair<vi, vi> EulerWalk(int n, vector<vector<pii>>& adj, int m, bool dir, bool cyc) {
  vi D(n), ptr(n), used(m), nodes, edges;
  vector<pii> st;
  int src = 0, bad = 0;
  for (int i = 0; i < n; ++i) {
    if (dir) for (auto& p : adj[i]) D[i]++, D[p.first]--;
    else D[i] = sz(adj[i]) & 1;
  }
  for (int i = 0; i < n; ++i) {
    if (sz(adj[i]) && adj[src].empty()) src = i;
    if (D[i]) {
      bad++;
      if ((dir && D[i] > 0) || (!dir)) src = i;
    }
  }
  if (bad > 2 || (cyc && bad) || (dir && bad && D[src] != 1)) return {};
  st.pb({src, -1});
  while (!st.empty()) {
    int u = st.back().first;
    if (ptr[u] < sz(adj[u])) {
      auto [v, id] = adj[u][ptr[u]++];
      if (!used[id]) used[id] = 1, st.pb({v, id});
    } else {
      auto [v, id] = st.back();
      st.pop_back();
      nodes.pb(v);
      if (id != -1) edges.pb(id);
    }
  }
  if (sz(edges) != m) return {};
  reverse(all(nodes)), reverse(all(edges));
  return {nodes, edges};
}

Back to top page