欧拉路的定义是：从图中某个点出发，遍历整个图，图中每条边通过且只能经过一次。而如果起点和终点也相同，就被称为欧拉回路。

欧拉路问题只要有两种：判断欧拉路的存在性、打印出欧拉路。欧拉路问题的解决主要通过处理度（Degree）。一个点的度数，是这个点上连接的边的数量。在无向图中，如果度数是偶数，则称这个点为偶点，反之则为奇点；在有向图中，因为边是有方向的，一个点的度又分为出度和入度两种。

欧拉路和欧拉回路的存在性判断

欧拉路存在的前提条件是联通图。因此要先用 DFS 或并查集判断图的连通性。

接着，根据图的种类（有向图或无向图）进行判断：

• 如果图是无向图，那么如果图中的点全都是偶点，则存在欧拉回路，并且任意点都可以作为起点和终点；如果图中只有两个奇点，则存在欧拉路，并且其中一个奇点是起点，另一个是终点。
• 如果图是有向图，那么如果图中所有点的度数都是 $0$，则存在欧拉回路；如果只有一个度数为 $1$ 的点，一个度数为 $-1$ 的点，则存在欧拉路，其中度数为 $1$ 的是起点，度数为 $-1$ 的是终点。

欧拉路的判断理解比较简单，可以结合 The Necklace 这道题进行巩固。

题目大意：有 $n$（$5 \leq n \leq 1000$）个珠子，每个珠子有两种颜色，分布在珠子的两侧。至多有 $50$ 种不同的颜色，用 $1$ 到 $50$ 的整数表示。求它们是否能复原成完整的项链，如果能，输出它们的方案。

把颜色抽象成点，每一个珠子的两种颜色相当于在点之间连了一条无向边。如果珠子能穿成一条完整的项链，就说明最终形成了一条欧拉回路。

#include <iostream>
#include <cctype>
#include <vector>
#include <string.h>

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 55;

int T;
int n;
int x, y;
int color;

int graph[maxN][maxN]; // 本题的节点数较少，直接用邻接矩阵表示
int degree[maxN];      // 存储度数

void DFS(int u)
{
    for (int v = 1; v <= 50; v++)
        if (graph[u][v])
        {
            graph[u][v]--;
            graph[v][u]--;
            DFS(v);
            printf("%d %d\n", v, u);
        }
}

int main()
{
    T = read();
    for (int t = 1; t <= T; t++)
    {
        printf("Case #%d\n", t);
        memset(graph, 0, sizeof(graph));
        memset(degree, 0, sizeof(degree));
        n = read();
        while (n--)
        {
            x = read(), y = read();
            color = x;
            degree[x]++;
            degree[y]++;
            graph[x][y]++;
            graph[y][x]++;
        }
        bool flag = true;
        for (int i = 1; i <= 50; i++)
            if (degree[i] % 2)
            {
                printf("some beads may be lost\n");
                flag = false;
                break;
            }
        if (flag)
            DFS(color);
        printf("\n");
    }
    return 0;
}

例题

Luogu P1341 无序字母对

和 The Necklace 有所不同的是，这道题无论是欧拉路还是欧拉回路都是可以的。同时，为了输出最后的欧拉（回）路，我们可以用栈进行存储。以及注意题目中对字典序的要求，这决定了我们 DFS 的起点。

#include <iostream>
#include <cctype>
#include <stack>

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 60;

int n;
int x, y;

int G[maxN][maxN];
int degree[maxN];
stack<int> st;

void DFS(int u)
{
    for (int v = 0; v <= 51; v++)
        if (G[u][v])
        {
            G[u][v]--;
            G[v][u]--;
            DFS(v);
            st.push(u);
        }
}

int main()
{
    n = read();
    while (n--)
    {
        string s;
        cin >> s;
        if (s[0] >= 'a' && s[0] <= 'z')
            x = s[0] - 'a' + 26;
        else if (s[0] >= 'A' && s[0] <= 'Z')
            x = s[0] - 'A';
        if (s[1] >= 'a' && s[1] <= 'z')
            y = s[1] - 'a' + 26;
        else if (s[1] >= 'A' && s[1] <= 'Z')
            y = s[1] - 'A';

        G[x][y]++;
        G[y][x]++;
        degree[x]++;
        degree[y]++;
    }

    int cnt = 0;
    int point1 = -1, point2 = -1;
    for (int i = 0; i <= 51; i++)
        if (degree[i] % 2)
        {
            cnt++;
            if (point1 == -1)
                point1 = i;
            else if (point2 == -1)
                point2 = i;
        }

    // 存在欧拉回路
    if (cnt == 0)
    {
        int word;
        for (int i = 0; i <= 51; i++)
            if (degree[i])
            {
                word = i;
                break;
            }
        st.push(word);
        DFS(word);
        while (!st.empty())
        {
            if (st.top() <= 25)
                printf("%c", st.top() + 'A');
            else
                printf("%c", st.top() - 26 + 'a');
            st.pop();
        }
    }
    else if (cnt == 2)
    {
        if (point1 > point2)
            swap(point1, point2);
        st.push(point2);
        DFS(point1);
        while (!st.empty())
        {
            if (st.top() <= 25)
                printf("%c", st.top() + 'A');
            else
                printf("%c", st.top() - 26 + 'a');
            st.pop();
        }
    }
    else
        printf("No Solution\n");
    return 0;
}