test/graph/euler.test.cpp

• View this file on GitHub
• Last update: 2025-10-17 22:12:07+08:00
• Problem: https://judge.yosupo.jp/problem/eulerian_trail_undirected

Depends on

• src/graph/euler.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/eulerian_trail_undirected
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using pii = pair<int, int>;

#include "../../src/graph/euler.hpp"

void solve() {
  int n, m;
  cin >> n >> m;
  map<pii, int> mp;
  Euler euler(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    mp[{u, v}] = mp[{v, u}] = i;
    euler.adde(u, v);
  }
  int resp = euler.work();
  if (resp == -1) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
    for (int i = 0; i <= m; i++) cout << euler.path[i] << " \n"[i == m];
    for (int i = 0; i < m; i++) cout << euler.epath[i] << " \n"[i + 1 == m];
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

#line 1 "test/graph/euler.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/eulerian_trail_undirected
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using pii = pair<int, int>;

#line 1 "src/graph/euler.hpp"
// 无向图欧拉回路或路径, 时间复杂度 $\mathcal{O}(n + m)$.
struct Euler {
  int n, m = 0;
  vector<char> used;
  vector<int> cur_e, path, epath;
  vector<vector<pii>> G;
  Euler(int n) : n(n), cur_e(n), G(n) {}
  void adde(int u, int v) { G[u].PUSHB({v, m}), G[v].PUSHB({u, m++}); }
  int work() {
    if (m == 0) return path.PUSHB(0), 0;
    used.assign(m, 0);
    vector<int> odd, even;
    for (int i = 0; i < n; i++)
      if (!G[i].empty()) G[i].size() & 1 ? odd.PUSHB(i) : even.PUSHB(i);
    if (odd.size() == 1 || odd.size() > 2) return -1;
    odd.empty() ? dfs(even[0]) : dfs(odd[0]);
    reverse(ALL(path)), reverse(ALL(epath));
    return int(path.size()) == m + 1 ? 0 : -1;
  }

 private:
  void dfs(int u) {
    for (int& i = cur_e[u]; i < int(G[u].size());) {
      auto [v, e] = G[u][i++];
      if (used[e]) continue;
      used[e] = 1, dfs(v), epath.PUSHB(e);
    }
    path.PUSHB(u);
  }
};
#line 9 "test/graph/euler.test.cpp"

void solve() {
  int n, m;
  cin >> n >> m;
  map<pii, int> mp;
  Euler euler(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    mp[{u, v}] = mp[{v, u}] = i;
    euler.adde(u, v);
  }
  int resp = euler.work();
  if (resp == -1) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
    for (int i = 0; i <= m; i++) cout << euler.path[i] << " \n"[i == m];
    for (int i = 0; i < m; i++) cout << euler.epath[i] << " \n"[i + 1 == m];
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	euler_tour_00	AC	285 ms	29 MB
g++	euler_tour_01	AC	289 ms	30 MB
g++	euler_tour_02	AC	269 ms	29 MB
g++	euler_tour_03	AC	287 ms	28 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	5 ms	4 MB
g++	many_same_vertex_00	AC	250 ms	39 MB
g++	many_same_vertex_01	AC	270 ms	41 MB
g++	many_same_vertex_02	AC	271 ms	42 MB
g++	max_random_00	AC	67 ms	8 MB
g++	max_random_01	AC	264 ms	29 MB
g++	max_random_02	AC	353 ms	42 MB
g++	max_random_walk_00	AC	95 ms	18 MB
g++	max_random_walk_01	AC	267 ms	38 MB
g++	max_random_walk_02	AC	417 ms	51 MB
g++	mid_random_00	AC	96 ms	5 MB
g++	mid_random_01	AC	97 ms	4 MB
g++	mid_random_02	AC	98 ms	5 MB
g++	mid_random_walk_00	AC	119 ms	5 MB
g++	mid_random_walk_01	AC	115 ms	5 MB
g++	mid_random_walk_02	AC	127 ms	5 MB
g++	small_random_00	AC	57 ms	4 MB
g++	small_random_01	AC	58 ms	4 MB
g++	small_random_02	AC	58 ms	4 MB
g++	small_random_walk_00	AC	72 ms	4 MB
g++	small_random_walk_01	AC	71 ms	4 MB
g++	small_random_walk_02	AC	71 ms	4 MB

Back to top page