拥有欧拉回路的无向图称为欧拉图

无向图从点S出发能够不重不漏的经过每条边一次(可重复经过图中节点)最后回到点S**称该路径为欧拉回路**,

1. 邻接表存图

2. dfs用栈保存回溯的点,最后栈的逆序就是欧拉回路

   技巧

3. 数据栈模拟递归

4. 访问一条边后head[x] = next1[i]将点x的第一条边改为下一个未访问的边,每次取出head[x]可以避免拿到访问过的边

POJ 2230

• 题目要求一条边正反都走,那么取消vis[]标记

  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  const int maxn = 100010;
  
  int head[maxn],next1[maxn*10],ver[maxn*10],tot;
  int stack1[maxn*10],ans[1000010];
  bool vis[maxn*10];
  int n,m,top,t;
  
  void add(int x,int y) {
      ver[++tot] = y;
      next1[tot] = head[x];
      head[x] = tot;
  }
  void euler() {
      stack1[++top] = 1;
      while (top > 0) {
          int x = stack1[top], i=head[x];
          while (i && vis[i]) i=next1[i];
          if (i) {
              stack1[++top] = ver[i];
              //vis[i] = vis[i^1] = 1;
              head[x] = next1[i];
          } else {
              top--;
              ans[++t] = x;
          }
      }
  }
  
  int main() {
      freopen("2.in","r",stdin);
      cin >> n >> m;
      tot = 1;
      for (int i=1; i<=m; ++i) {
          int x,y;
          scanf("%d%d",&x,&y);
          add(x,y);
          add(y,x);
      }
      euler();
      for (int i=t; i; --i)
          printf("%d\n",ans[i]);
      return 0;
  }