欧拉路径：经过图中每条边恰好一次的路径。

欧拉回路：经过图中每条边恰好一次的回路（起点和终点相同）。

注：

• 欧拉路径和欧拉回路对不限制点的经过次数，可重复经过一个点。
• 正因为不限制点，所以求欧拉路径/回路应当先去掉孤立点（即入度和出度都为 $0$ 的点）。

判定：

• 有向图
  • 欧拉路径：图中恰好存在 $1$ 个点出度比入度多 $1$（该点为起点），恰好存在 $1$ 个点入度多 $1$（该点为终点），其余点入度等于出度。
  • 欧拉回路：所有点的入度等于出现，起点和终点可以是任意点。
• 无向图
  • 欧拉路径：图中恰好有两个点的度数为奇数（这两个点为起点和终点，起点和终点可互换），其余点的度数为偶数。
  • 欧拉回路：所有点的度数都为偶数，起点和终点任意。

注：因为欧拉路径/回路显然是在连通块上考虑的，若图中有多个连通块，每个连通块都符合条件，那么整个图也是符合条件的，但是显然没有整个图的欧拉路径/回路。所以欧拉路径/回路的前置条件是整个图是连通图。

求解：

有向图欧拉路径：

根据判定条件，找到唯一的那一个出度$=$入度$+1$ 的点作为起点，dfs 递归第一次经过某条边，递归前删除这条边。

有向图欧拉回路：

根据判定条件，可以任选一个点作为起点，dfs 递归第一次经过某条边，递归前删除这条边。

无向图欧拉路径：

根据判定条件，找到度数为奇数的一个点，作为起点，dfs 递归第一次经过某条边，递归前删除这条边。

无向图欧拉回路：

根据判定条件，可以任选一个点作为起点，dfs 递归第一次经过某条边，递归前删除这条边。

注：无向图需要注意标记把同一条边的反边也给删了。

注：上述四种情况的算法实现流程完全一致。

时间复杂度：$O(n+m)$。

有向图：

void dfs(int x) {
    for (unsigned i = del[x]; i < p[x].size(); i = del[x]) {
        del[x]++;
        dfs(p[x][i]);
    }
    ans.push_back(x);
}

无向图：

void dfs(int x) {
    for (unsigned i = del[x]; i < p[x].size(); i = del[x]) {
        del[x]++;
        auto [u, id] = p[x][i];
        if (vis[abs(id)])
            continue;
        vis[abs(id)] = 1;
        dfs(u);
        ans.push_back(id);
    }
}