$O(N+M)$非递归版代码 防止栈溢出

欧拉回路就是给一个图，存在一条回路把所边经过且每条边只经过一次。

对于无向图：

存在欧拉回路的条件：每个点的度都为偶数；

存在欧拉路的条件：有且只有两个点的度为一，且这两个点分别为起点和终点；

对于有向图：

存在欧拉回路的条件：每个点出度等于入度；

存在欧拉路的条件：存在一个点出度比入度多一作为起点，存在一点入度比出度多一作为终点，其余点出度等于入度；

求欧拉回路的方法——基本（套圆）法
　　dfs搜索，不能再往下走便回溯，回溯时记录路径，回溯时不清除对边的标记，最后求出来的路径就是欧拉回路。

举例

（1）走$<1,2>,<2,3>, < 3,4>,<4,5>,<5,1>$,然后无路可走，就回溯记录下回溯路径$<1,5>,<5,4>$,4点有其它路壳走。
（2）$<4,8>,<8,3>,<3,6>,<6,7>,<7,2>，<2,4>$,无路可走，然后回溯$<1,5>,<5,4>,<4,2>,<2,7>,<7,6>,<6,3>,<3,8>,<8,4>,<4,3>,<3,2>,<2,1>$。
记录下的路径$<1,5>,<5,4>,<4,2>,<2,7>,<7,6>,<6,3>,<3,8>,<8,4>,<4,3>,<3,2>,<2,1>$便是一条欧拉回路。

上述的时间复杂度为$O(NM)$。因为一个点会被重复遍历多次。
假设我们采用邻接表存储无向图，我们可以在访问一条边$(x,y)$后，及时地修改表头$head[x]$，令它指向下一条边，这样我们每次只需取出$head[x]$,就自然跳过了所有已经访问过的边。（vis数组突然就没什么用了）

另外，因为欧拉回路的DFS的递归层数是$O(M)$级别的，很容易造成系统栈的溢出，我们可以用另一个栈，模拟机器的递归过程，把代码转化为非递归实现，优化后的程序时间复杂度为$O(N+M)$

---

——《算法竞赛进阶指南》

回到本题，由于题目要求每条边要正反走两边，那么我们直接把原求欧拉回路模板的vis数组的双向标记改为单向标记即可。因为按照一般的存储方式，无向边在邻接表中是被拆成了两条有向边来存储，若无标记，根据欧拉回路中的更新方式来看，正好会经过两次。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<math.h>
#include<cstring>
#include<queue>
//#define ls (p<<1)
//#define rs (p<<1|1)
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
//#define lowbit(p) p&(-p)
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const ll INF = 1e18;
const int N = 5e4+7;
const int M = 5e5+7;

int head[N],nex[M],ver[M],tot = 1;
bool vis[M];
int stk[M],ans[M];//模拟系统栈，答案栈
int n,m,s,t,cnt,top;
queue<int>q;

void add(int x,int y){
    ver[++tot] = y;nex[tot] = head[x];head[x] = tot;
}

void euler(){//模拟dfs
    stk[++top] = 1;//起点
    while(top > 0){
        int x = stk[top],i = head[x];
        while(i && vis[i])i = nex[i];//找到一条尚未访问过的路
        // 与x相连的所有边均已访问，模拟回溯过程，并记录
        if(i){
            stk[++top] = ver[i];
            vis[i] =  true;//题目要求要回来的嘛，需要标记一次
            //vis[i] = ver[i ^ 1] = true;//正常的欧拉回路模板
            head[x] = nex[i];
        }
        else {// 与x相连的所有边均已访问，模拟回溯过程，并记录
            top--;
            ans[++cnt] = x;
        }

    }
}

int main(){
    scanf("%d%d",&n,&m);
    tot = 1;
    over(i,1,m){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    euler();
    over(i,1,cnt)
    printf("%d\n",ans[i]);
}