概念：
欧拉路径：图G中的一条路径，能够通过图中的每一条边，并且每条边仅通过一次；
欧拉回路：起点终点相同得欧拉路径；
欧拉图: 包含欧拉回路的图；

结论：
1.对于无向图(所有边都是连通的)
    (1)存在欧拉路径 <=> 度数为奇数的点只有0或2个
    (2)存在欧拉回路 <=> 度数为奇数的点只有0个

2.对于有向图(所有边都是连通的)
    (1)存在欧拉路径 <=> (所有点din=dout)或(除了两个点之外(一个din=dout+1,一个dout=din+1)，所有点din=dout)
    (2)存在欧拉回径 <=> 所有点din=dout

处理两大问题：

1. 如何判断图中是否存在欧拉路径(回路)？ 

答：两个方面: (1)用上面的结论 (2)判断图中边的连通性 
    (1)代码中用数组记录点的(出入)度数，用上面的结论
    (2)所有边要在一个连通块内，点无所谓(即可以有孤立的点); 可以用 dfs 或 并查集 来判断边的连通性   
        dfs: 找起点，从起点开始遍历图，统计边数，看是否=m
        并查集：判断所有出现过的点是否在同一个集合内(个人认为有孤立点时不能用) 


2. 如何求出欧拉路径(回路)？

答：找起点start，从start开始dfs，大致代码如下
    void dfs(int u)
    {
        for(遍历u的邻边i)
        {
            //删边 等操作
            dfs( j(邻接点) );

            //把j加入答案队列中 seq <- j; 
        }
    }
    注意main()中把seq <- start
    最后反向输出seq;

注意几个细节：
1. 关于优化的问题，具体看下面板子(O(nm) -> O(n+m)) 
2. 注意dfs完记得seq <- start
3. 若要输出字典序最小的欧拉路，则我们在搜时从小到大枚举就行 
4. 注意最后逆序输出
5. 注意要找起点(有向图:dout=din+1的点；无向图:度数为奇数的点)！！！从起点开始搜！

有/无向图中判断(输出)欧拉回路 优化版(Acwing 1184)

int n,m,type;   //type=1表示无向图，=0表示有向图
int h[N],ne[M],e[M],idx;
bool vis[M];    //标记一下每条边是否走过
int din[N],dout[N]; //标记入度出度

int ans[M],cnt; //cnt表示答案路径的长度

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for(int &i=h[u];i!=-1;)   //加一点玄学优化
    {
        if(vis[i])    //该边被用过
        {
            i = ne[i];   //直接删掉(优化)
            continue;
        }

        vis[i] = true;  //标记被用过
        if(type == 1)   //是无向图
            vis[i ^ 1] = true;  //标记反向边(i^1)用过

        int t;   
        if(type == 1)   //无向图边的表示是成对的(0,1)一条 (2,3)一条...
        {
            t = i/2 + 1;    //t表示该点是多少
            if(i & 1) t = -t;  //i是反向边，t*=-1(根据题目意思写)
        }
        else t = i + 1; //有向图

        int j = e[i];
        i = ne[i];  //边用过之后直接删了
        dfs(j);

        ans[++cnt] = t;     //回溯时再记录答案
    }
}

int main()
{
    scanf("%d", &type);
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);

        add(a, b);
        if (type == 1) add(b, a);
        din[b] ++ , dout[a] ++ ;
    }

    //下面判断无解
    if(type == 1)   //无向图
    {
        for(int i=1;i<=n;i++)
            if((din[i] + dout[i]) % 2 == 1)
            {
                puts("NO");
                return 0;
            }
    }
    else    //有向图
    {
        for(int i=1;i<=n;i++)
            if(din[i] != dout[i])
            {
                puts("NO");
                return 0;
            }
    }

    //下面dfs，顺便判断边是否连通
    for(int i=1;i<=n;i++)
        if(h[i] != -1)    //有边的点
        {
            dfs(i);
            break;
        }

    if(cnt < m) //边不连通
    {
        puts("NO");
        return 0;
    }

    puts("YES");
    for(int i=cnt;i;i--) printf("%d ",ans[i]);
    puts("");

    return 0;
}

无向图中，求一条字典序最小的欧拉路径(Acwing 1124)

int n=500,m;
int g[N][N];    //邻接矩阵
int ans[M],cnt; //注意这里答案和边数有关
int d[N];   //度数

void dfs(int u)
{
    for(int i=1;i<=n;i++)
        if(g[u][i]) //u i之间有边
        {
            g[u][i]--; g[i][u]--;   //删掉边(优化)
            dfs(i);     //先dfs，不能先存点

            ans[++cnt] = i;     //回溯时存点(统一一下，放在for里面)
        }
}

int main()
{
    cin>>m;
    while (m -- )
    {
        int a,b;
        cin>>a>>b;
        g[a][b] ++; g[b][a] ++;
        d[a] ++; d[b] ++;
    }

    int start = 1;  //找一下起点
    while(!d[start]) start ++;
    for(int i=1;i<=n;i++)   //度数为奇数的点为起点
        if(d[i] % 2)
        {
            start = i;
            break;
        }

    dfs(start); //从起点开始搜
    ans[++cnt] = start; //别忘了加起点

    for(int i=cnt;i;i--) cout<<ans[i]<<endl;

    return 0;
}

有向图中，判断欧拉路径(并查集版)(Acwing 1185)

din[]入度   dout[]出度

    //下面判断除了起点终点 所有点的入度出度是否相等
    int start = 0,en = 0;
    bool flag = true;   //标记是否成功
    for(int i=0;i<n;i++)   //遍历所有点
        if(din[i] != dout[i])
        {
            if(din[i] == dout[i] + 1) en++; //终点
            else if(dout[i] == din[i] + 1) start++; //起点
            else
            {
                flag = false;
                break;
            }
        }

    //判断是否有且只有一个start和end
    if(flag && !(start==0 && en==0 || start==1 && en==1)) flag = false;

    //下面判断是否连通(看一下所有出现过的点是否在一个集合中)
    int fx = -1;
    for(int i=0;i<n;i++)   //遍历所有出现过的点
        if(vis[i])  //出现过
        {
            if(fx == -1) fx = find(i);
            else if(fx != find(i))  //不连通
            {
                flag = false;
                break;
            }
        }