欧拉图：

对于应该连通图G，有：

1欧拉路径：一条路径，它能够不重复地遍历完所有的边，这个性质很像不重复地一笔画完所有边，所以有些涉及到欧拉路径的问题叫做一笔画问题。

2欧拉回路：一条路径，它能够不重复地遍历完所有的边，并且回到起点，可以看出欧拉回路也是欧拉路径。

3半欧拉图：一个图，图中存在欧拉路径。

4欧拉图(E图)：一个图，图中存在欧拉回路，可以看出欧拉图也是半欧拉图。

 先判断欧拉图：

 用希尔霍尔(Hierholzer)算法(基于DFS/套圈法)找欧拉路径/欧拉回路 区别(起点终点是否相同)

如果不是回路那起点固定，如果是回路，那起点不固定。

 

 注意先dfs再入栈

已经判断是无向欧拉图了，下面开始找欧拉回路，代码如下：时间复杂度为O(m*(n+m))

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n, m;
const int maxv = 1005;
const int maxe = 1005;
struct edge {int v, next;int eid;//本条边的编号bool del;//=1说明被遍历过，被删除掉了
}e[maxe * 2];//无向图边×2
int head[maxv];
int cnt;
stack<int>ansv;
void add(int x, int y) {e[cnt].v = y;e[cnt].next = head[x];e[cnt].eid = cnt;e[cnt].del = 0;head[x] = cnt++;
}
void dfs(int x) {for (int i = head[x]; i != -1; i = e[i].next) {if (e[i].del == 1) continue;e[i].del = 1;e[i ^ 1].del = 1;//反向边dfs(e[i].v);}ansv.push(x);
}int main() {int x, y;scanf("%d %d", &n, &m);memset(head, -1, sizeof(head));for (int i = 1; i <= m; i++) {scanf("%d %d", &x, &y);add(x, y);add(y, x);}dfs(1);while (!ansv.empty()) {printf("%d ", ansv.top());ansv.pop();}printf("\n");return 0;
}
//6 9
//1 2
//1 3
//2 3
//3 5
//5 4
//3 4
//4 7
//7 6
//4 6

下面进行弧优化时间复杂度降为O(n+m)

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n, m;
const int maxv = 1005;
const int maxe = 1005;
struct edge {int v, next;int eid;//本条边的编号bool del;//=1说明被遍历过，被删除掉了
}e[maxe * 2];//无向图边×2
int head[maxv];
int cnt;
stack<int>ansv;
void add(int x, int y) {e[cnt].v = y;e[cnt].next = head[x];e[cnt].eid = cnt;e[cnt].del = 0;head[x] = cnt++;
}
//弧优化
void dfs(int x) {//时间复杂度从O((n+m)*m)到O(n+m)for (int i = head[x]; i != -1; i = head[x]) {//巧妙的改动，第二次删掉且不会死循环if (e[i].del == 1) {head[x] = e[i].next;//指向下一条continue;}e[i].del = 1;e[i ^ 1].del = 1;//反向边dfs(e[i].v);}ansv.push(x);
}int main() {int x, y;scanf("%d %d", &n, &m);memset(head, -1, sizeof(head));for (int i = 1; i <= m; i++) {scanf("%d %d", &x, &y);add(x, y);add(y, x);}dfs(1);while (!ansv.empty()) {printf("%d ", ansv.top());ansv.pop();}printf("\n");return 0;
}
//6 9
//1 2
//1 3
//2 3
//3 5
//5 4
//3 4
//4 7
//7 6
//4 6