定义

欧拉路径（欧拉通路）：通过图中所有边的简单路。（换句话说，每条边都通过且仅通过一次）也叫”一笔画”问题。
欧拉回路：闭合的欧拉路径。（即一个环，保证每条边都通过且仅通过一次）
欧拉图：包含欧拉回路的图。

起源

在一个图中求解一条欧拉回路的问题，起源于欧拉提出的、著名的“七桥问题”。详见百度百科。

判定

欧拉路径：

1.图G是连通的，无孤立点。
2.无向图奇点数为0或2，并且这两个奇点其中一个为起点另外一个为终点。有向图，可以存在两个点，其入度不等于出度，其中一个入度比出度大1，为路径的起点；另外一个出度比入度大1，为路径的终点。

欧拉回路

1.图G是连通的，无孤立点。
2.无向图奇点数为0；有向图每个点的入度必须等于出度。

算法

求欧拉回路的算法中，普遍使用的是Fleury算法和Hierholzer算法。由于Hierholzer算法在时间复杂度和代码实现上都更优，所以这里只介绍一下Hierholzer算法。~~主要是我不会敲Fleury……~~

Hierholzer算法思路

1.根据每个点的入度选择起点。
2.运用DFS去遍历当前节点的每一条边，之后将该节点压入栈中。
3.操作2接受后，栈中的元素就是一条欧拉回路。

附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;

int n,m,x,y,head[1200],cnt,map[1030][1030],d[1030],begin,s[1030],t;

void dfs(int k)
{
    for(register int i = 1; i <= n; i++)
    {
        if(map[k][i] > 0)
        {
            map[k][i] --;
            map[i][k] --;
            dfs(i);
        }
    }
    s[++t] = k;
}

int main()
{
    scanf("%d",&m);
    for(register int i = 1; i <= m; i++)
    {
        scanf("%d%d",&x,&y);
        map[x][y] ++;
        map[y][x] ++;
        n = max(n,x);
        n = max(n,y);
        d[x] ++;
        d[y] ++;
    }
    for(register int i = 1; i <= n; i++)
    {
        if(d[i] % 2 == 1) 
        {
            begin = i;
            break;
        }
    }
    if(begin == 0) begin = 1;
    dfs(begin); 
    for(register int i = t; i >0; i--) printf("%d\n",s[i]);
    printf("\n"); 
    return 0;
}

推荐联系题目：骑马修栅栏、无序字母对