题解：欧拉回路问题

一、题目背景

给定一张图（无向图或有向图），需要找出图中的欧拉回路，即一个经过每条边恰好一次的环。

二、解题思路

本题通过判断图的性质（节点度数）来确定是否存在欧拉回路，然后使用深度优先搜索（DFS）来寻找欧拉回路。对于无向图，所有节点的度数必须为偶数；对于有向图，每个节点的入度必须等于出度。在搜索过程中，记录经过的边，并最终判断是否遍历了所有边来确定是否存在欧拉回路。

具体步骤如下：
1. 定义相关数组和变量，包括存储图的邻接表的数组 h[N]、e[M]、ne[M]，标记边是否被使用的数组 used[M]，存储结果的数组 ans[M]，记录节点入度和出度的数组 din[N]、dout[N]，以及图的类型 type、节点数 n、边数 m 等。
2. 编写添加边的函数 add，用于构建图的邻接表。
3. 编写深度优先搜索函数 dfs：
- 遍历当前节点 u 的所有邻接边。
- 若边已被使用，则跳过。
- 标记当前边和（无向图时）其反向边为已使用。
- 根据图的类型计算边的编号 t。
- 递归访问邻接节点 j，并在回溯时将边的编号记录到结果数组 ans 中。
4. 在 main 函数中：
- 读取图的类型、节点数和边数，初始化邻接表。
- 读取每条边的信息，构建图的邻接表，并更新节点的入度和出度。
- 根据图的类型判断是否存在欧拉回路的条件（无向图节点度数为偶数，有向图节点入度等于出度），若不满足则输出 NO 并结束程序。
- 从第一个有邻接边的节点开始进行深度优先搜索。
- 判断搜索过程中记录的边数是否等于总边数，若不相等则输出 NO 并结束程序。
- 若存在欧拉回路，输出 YES 和欧拉回路经过的边的编号（逆序输出）。

三、代码逐段分析

（一）头文件和全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010;

int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];

1. 头文件：包含了标准输入输出（cstdio 和 iostream）、字符串操作（cstring）和算法（algorithm）相关的头文件，并使用标准命名空间。
2. 常量定义：const int N = 100010, M = 400010; 定义节点和边的最大数量。
3. 变量定义：
   • int type;：存储图的类型，1 表示无向图，2 表示有向图。
   • int n, m;：分别表示图的节点数和边数。
   • int h[N], e[M], ne[M], idx;：用于构建邻接表，h[N] 存储每个节点的第一条边的编号，e[M] 存储边的终点，ne[M] 存储同一起点下一条边的编号，idx 用于记录边的编号。
   • bool used[M];：标记每条边是否已被使用。
   • int ans[M], cnt;：ans[M] 存储欧拉回路经过的边的编号，cnt 记录已记录的边数。
   • int din[N], dout[N];：分别记录每个节点的入度和出度。

（二）添加边函数 add

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

将一条从节点 a 到节点 b 的边添加到邻接表中。

（三）深度优先搜索函数 dfs

void dfs(int u)
{
    for (int &i = h[u]; ~i;)
    {
        if (used[i])
        {
            i = ne[i];
            continue;
        }

        used[i] = true;
        if (type == 1) used[i ^ 1] = true;

        int t;

        if (type == 1)
        {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        }
        else t = i + 1;

        int j = e[i];
        i = ne[i];
        dfs(j);

        ans[ ++ cnt] = t;
    }
}

1. 从节点 u 开始深度优先搜索：
   • 遍历节点 u 的所有邻接边，若边已被使用，则跳过。
   • 标记当前边为已使用，对于无向图，同时标记其反向边为已使用（通过 i ^ 1 实现）。
   • 根据图的类型计算边的编号 t：
     • 无向图中，t = i / 2 + 1，若 i 为奇数则取负号。
     • 有向图中，t = i + 1。
   • 记录邻接节点 j，将当前边指向下一条边，递归访问节点 j。
   • 回溯时将边的编号 t 记录到结果数组 ans 中。

（四）main 函数

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] & 1)
            {
                puts("NO");
                return 0;
            }
    }
    else
    {
        for (int i = 1; i <= n; i ++ )
            if (din[i] != dout[i])
            {
                puts("NO");
                return 0;
            }
    }

    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;
}

1. 读取图的类型、节点数和边数，初始化邻接表。
2. 读取每条边的信息，构建图的邻接表：
   • 对于无向图，添加两条边（a 到 b 和 b 到 a）。
   • 更新节点的入度和出度。
3. 根据图的类型判断是否存在欧拉回路的条件：
   • 无向图中，检查所有节点的度数是否为偶数，若存在奇数度数的节点，则输出 NO 并结束程序。
   • 有向图中，检查所有节点的入度是否等于出度，若不相等，则输出 NO 并结束程序。
4. 从第一个有邻接边的节点开始进行深度优先搜索。
5. 判断搜索过程中记录的边数是否等于总边数，若小于总边数，则输出 NO 并结束程序。
6. 若存在欧拉回路，输出 YES 和欧拉回路经过的边的编号（逆序输出）。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 建图：读取边的信息并构建邻接表，时间复杂度为 (O(m))，其中 (m) 是边数。
2. 判断条件：检查节点度数或入度出度，时间复杂度为 (O(n))，其中 (n) 是节点数。
3. 深度优先搜索：每个边最多被访问一次，时间复杂度为 (O(m))。
   总体时间复杂度为 (O(m + n))。

（二）空间复杂度

1. 数组空间：邻接表相关数组 h[N]、e[M]、ne[M]，标记数组 used[M]，结果数组 ans[M]，入度出度数组 din[N]、dout[N] 等，空间复杂度为 (O(m + n))。
   总体空间复杂度为 (O(m + n))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。