基础概念

前提：连通图
无向图：
欧拉通路：存在欧拉通路的充要条件是度数为奇数的点只能有0或2个
欧拉回路：存在欧拉回路的充要条件是度数为奇数的点只能有0个

有向图：
欧拉通路：存在欧拉通路的充要条件是要么所有点的入度等于出度，要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点一个满足入度比出度大一，另一个满足出度比入度大一。
欧拉回路：存在欧拉回路的充要条件是所有节点的出度均等于入度。

代码实现：

  1. // 不做优化的处理方式
  2. // 边
  3. dfs(u) {
  4.     for (v : edge[u]) {
  5.         if (used[v]) continue; // 针对无向图才有
  6.         dfs(v);
  7.         q[++tt] = v;
  8.     }
  9. }
  11. // 点
  12. dfs(u) {
  13.      for (v : edge[u]) {
  14.         if (used[v]) continue; // 针对无向图才有
  15.         dfs(v);    
  16.     }
  17.     q[++tt] = u;
  18. }

模板

  1. 记录欧陆通路/欧拉回路经过的边

本质是记录最后一条被遍历的边
AcWing 1184. 欧拉回路
如果不做优化，最坏时间复杂度为O(m2)
优化的做法是边dfs边删除边，防止再次遍历到该点时所有出边又被遍历一次。

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static final int N = 100010, M = 400010;
  6.     static int[] h = new int[N], e = new int[M], ne = new int[M];
  7.     static int[] res = new int[M];
  8.     static int idx, cnt;
  9.     static int type, n, m;
  10.     static boolean[] used = new boolean[M];
  11.     static int[] din = new int[N], dout = new int[N];
  12.     public static void main(String[] args) throws IOException {
  13.         var sc = new Scanner(); // 换成Fast IO
  14.         type = sc.nextInt();
  15.         n = sc.nextInt();
  16.         m = sc.nextInt();
  18.         Arrays.fill(h, -1);
  19.         for (int i = 0; i < m; i++) {
  20.             int a = sc.nextInt(), b = sc.nextInt();
  21.             add(a, b);
  22.             if (type == 1) add(b, a);
  23.             din[b]++;
  24.             dout[a]++;
  25.         }
  27.         if (type == 1) {
  28.             for (int i = 1; i <= n; i++) {
  29.                 if ((din[i] + dout[i]) % 2 == 1) {
  30.                     System.out.println("NO");
  31.                     return;
  32.                 }
  33.             }
  34.         } else {
  35.             for (int i = 1; i <= n; i++) {
  36.                 if (din[i] != dout[i]) {
  37.                     System.out.println("NO");
  38.                     return;
  39.                 }
  40.             }
  41.         }
  43.         for (int i = 1; i <= n; i++) {
  44.             if (h[i] != -1) {
  45.                 dfs(i);
  46.                 break;
  47.             }
  48.         }
  50.         if (cnt != m) {
  51.             System.out.println("NO");
  52.             return;
  53.         }
  55.         System.out.println("YES");
  56.         for (int i = m; i > 0; i--)
  57.             System.out.print(res[i] + " ");
  58.         System.out.println();
  59.     }
  61.     static void dfs(int u) {
  62.         while (h[u] != -1) {
  63.             int i = h[u];
  64.             if (used[i]) {
  65.                 h[u] = ne[i];
  66.                 continue;
  67.             }
  69.             used[i] = true;
  70.             if (type == 1) used[i ^ 1] = true;
  71.             h[u] = ne[i];
  72.             int t;
  73.             if (type == 1) {
  74.                 t = i / 2 + 1;
  75.                 if (i % 2 == 1) t = -t;
  76.             } else t = i + 1;
  77.             dfs(e[i]);
  78.             res[++cnt] = t;
  79.         }
  80.     }
  83.     static void add(int a, int b) {
  84.         e[idx] = b;
  85.         ne[idx] = h[a];
  86.         h[a] = idx++;
  87.     }
  88. }
  1. 记录欧拉通路/欧拉回路经过的点

本质是记录最后一个被遍历的点
AcWing 1124. 骑马修栅栏
求欧拉回路/欧拉通路的最小字典序路径上的点
直接暴力做就行，不需要删边优化

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 510, M = 1500;
  5.     static int[][] g = new int[N][N];
  6.     static int n, m;
  7.     static int cnt;
  8.     static int[] res = new int[M];
  9.     static int[] din = new int[N], dout = new int[N];
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  13.         m = sc.nextInt();
  14.         int min = N;
  15.         for (int i = 1; i <= m; i++) {
  16.             int a = sc.nextInt(), b = sc.nextInt();
  17.             g[a][b]++;
  18.             g[b][a]++;
  19.             min = Math.min(min, a);
  20.             min = Math.min(min, b);
  21.             din[b]++;
  22.             dout[a]++;
  23.         }
  26.         for (int i = 1; i < N; i++) {
  27.             if ((din[i] + dout[i]) % 2 == 1) {
  28.                 min = i;
  29.                 break;
  30.             }
  31.         }
  33.         dfs(min);
  34.         for (int i = cnt; i > 0; i--)
  35.             System.out.println(res[i]);
  36.     }
  38.     static void dfs(int u) {
  39.         for (int i = 1; i < N; i++) {
  40.             if (g[u][i] > 0) {
  41.                 g[u][i]--;
  42.                 g[i][u]--;
  43.                 dfs(i);
  44.             }
  45.         }
  46.         res[++cnt] = u;
  47.     }
  49. }

应用

AcWing 1123. 铲雪车
欧拉回路，脑筋急转弯题目 + 数学
AcWing 1185. 单词游戏
判断图是否为欧拉回路或欧拉通路