题目地址：
https://www.acwing.com/problem/content/1186/
给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
输入格式：
第一行包含一个整数t tt，t ∈ { 1 , 2 } t∈\{1,2\}t∈{1,2}，如果t = 1 t=1t=1，表示所给图为无向图，如果t = 2 t=2t=2，表示所给图为有向图。第二行包含两个整数n , m n,mn,m，表示图的结点数和边数。接下来m mm行中，第i ii行两个整数v i , u i v_i,u_ivi,ui，表示第i ii条边（从1 11开始编号）。如果t = 1 t=1t=1则表示v i v_ivi到u i u_iui有一条无向边。如果t = 2 t=2t=2则表示v i v_ivi到u i u_iui有一条有向边。图中可能有重边也可能有自环。点的编号从1 11到n nn。
输出格式：
如果无法一笔画出欧拉回路，则输出一行：NO。否则，输出一行：YES，接下来一行输出任意一组合法方案即可。如果t = 1 t=1t=1，输出m mm个整数p 1 , p 2 , … , p m p_1,p_2,…,p_mp1,p2,…,pm。令e = ∣ p i ∣ e=|p_i|e=∣pi∣，那么e ee表示经过的第i ii条边的编号。如果p i p_ipi为正数表示从v e v_eve走到u e u_eue，否则表示从u e u_eue走到v e v_eve。如果t = 2 t=2t=2，输出m mm个整数p 1 , p 2 , … , p m p_1,p_2,…,p_mp1,p2,…,pm。其中p i p_ipi表示经过的第i ii条边的编号。
数据范围：
1 ≤ n ≤ 1 0 5 1≤n≤10^51≤n≤105
0 ≤ m ≤ 2 × 1 0 5 0≤m≤2×10^50≤m≤2×105
一个无向图含欧拉回路，当且仅当其边连通并且每个顶点的度是偶数。证明如下：
必要性：如果存在欧拉回路，则取该回路，其经过的所有顶点必然是有入边必有出边（除了出发点，对于出发点是有出必有入），所以该路径上的所有点的度是偶数。而孤立点的度是0 00，也是偶数，所以得证。
充分性：如果每个顶点的度都是偶数，那么从任一点出发，先走出一个回路，这样的回路一定是能走出来的，因为每次到一个顶点的时候，有入必有出，除非走回出发点，否则就能一直走下去，直到走到出发点为止。如果该回路已经包含了所有边了，那就找到了一条欧拉回路了；否则，从原图中删去该欧拉回路以及所有的孤立顶点，所得子图依然是所有点都是度为偶数的子图，并且它与欧拉回路一定存在公共顶点u uu，从u uu再重复上述过程（这里也可以类似数学归纳法来做，按归纳假设，求出从u uu出发的欧拉回路），然后将这个回路拼到原回路上去即可。
而对于一个有向图是否含欧拉回路，也有个充要条件，即其边连通，并且每个点的入度等于出度。证明类似无向图的情形。
无论其是有向图还是无向图，算法都是一样的。
首先考虑建图，我们依然是用链式前向星（即邻接表）来建图，对于无向图，由于某条边有可能是走正向，也有可能是走负向，这无法确定，所以我们要建立双向边，但是标记访问过的时候，需要在正向走过的时候同时再标记一下负向也走过了（反之亦然）。由于每次建立一条边的时候，我们都会同时建立其反向边，正向边在数组中的下标是偶数，反向边在数组中的下标是奇数（即一条正向反向边的下标分别是( 0 , 1 ) , ( 2 , 3 ) , . . . (0,1),(2,3),...(0,1),(2,3),...这样，正向边都是偶数，反向边都是奇数），有必要梳理出某条边在数组中的编号、该边本身的编号以及其反向边的编号之间的关系。如果在输入里，某条边的编号是k kk（从0 00计数。注意在题目里是从1 11计数的，所以最后还要加上1 11），那么其本身在数组中的编号就是2 k 2k2k，而其反向边的编号是2 k + 1 2k+12k+1；而如果知道了一条边在数组中的下标，那么其对应的反向边的编号取决于其自己是奇数还是偶数，如果是偶数则减1 11，否则是加1 11，在代码里可以用异或来做，具体来说就是2 k ∧ 1 = 2 k + 1 , ( 2 k + 1 ) ∧ 1 = 2 k 2k\wedge 1=2k+1,(2k+1)\wedge 1=2k2k∧1=2k+1,(2k+1)∧1=2k。
其次考虑算法，这可以用DFS后序遍历来做。之所以不用前序遍历，是因为在搜索的顺序的边与边之间不一定是邻接的，搜索出来的路径也不是一条连通的路径。而后序遍历则不然，如果确实存在欧拉路径，在分叉处的一条路回溯到分叉点的时候，如果该分叉处的所有树枝都被遍历过了，那么回溯的路径就是一条完整连续的路径，其本身就是一条欧拉路；如果还有树枝没遍历，则会按照该路继续DFS，而这次DFS一定还会回到分叉点，所以回溯的时候刚好会形成一个连通的路径，并且会把所有边都含到路径里去。即后序遍历，既不遗漏，又产生了连通的路径，完美解决了问题。
对于本题，可以先去找一个非孤立点，如果找不到的话则看边数是否是0 00，如果是0 00那确实是欧拉图（说明该图的所有点都是孤立点），否则的话，就从其中任意一个非孤立点开始做DFS，遍历过的边不再遍历，同时在回溯之前将当前边加入答案。这里有一个细节可以优化，如果我们只是对遍历过的边，用个bool数组进行标记的话，那么事实上仍然会遍历这一串指针，这也是会消耗很多时间的。所以，我们可以将遍历过的边直接删掉。但是由于我们的存储方式，对于正在遍历的那条边的反向边而言，即使知道它在数组中的下标，仍然不方便删，原因是我们是按照单链表的方式存的，要删就要从起点一步步向后找。所以我们采取的方案是，对于顶点v vv，从h [ v ] h[v]h[v]开始遍历其所有邻边的时候，如果是有向图，那非常简单，遍历完这条边立刻删掉即可；而对于无向图，则要先用一个bool数组标记其反向边为访问过，下次遍历这条反向边的时候由于已经标记过，那时再将其删去。
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
// 要建反向边，所以边数要开两倍
const int N = 100100, M = 400100;
int h[N], e[M], ne[M], idx;
int res[M], cnt;
// 记录某条边是否被访问过（主要是应付无向图的反向边）
bool used[M];
// din[i]和dout[i]分别记录顶点i的入度和出度
int din[N], dout[N];
int n, m;
// 记录图的类型，1表示无向图，2表示有向图
int type;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
// 注意，这里不是i = ne[i]，而是i = h[u]，因为每次遍历完一条边就顺便删掉了
for(int i = h[u]; ~i ;i = h[u]) {
// 删掉当前边
h[u] = ne[i];
// 如果i是已经用过的某条边的反向边，则直接略过
if (used[i]) continue;
// 标记这条边已使用。其实这句话可以省去不写，后面
// 的代码可以看出这个循环结束后这条边就已经被删了
// used[i] = true;
// 如果是无向图，那么这条边的反向边也要标记使用过了
if (type == 1) used[i ^ 1] = true;
int t;
if (type == 1) {
t = i / 2 + 1;
// (0, 1) (2, 3) (4, 5)奇数编号是返回的边
if (i & 1) t = -t;
} else t = i + 1;
dfs(e[i]);
// 回溯之前存路径
res[cnt++] = t;
}
}
int main() {
scanf("%d%d%d", &type, &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]) {
dfs(i);
break;
}
if (cnt < m) puts("NO");
else {
puts("YES");
for (int i = cnt - 1; i >= 0; i--)
printf("%d ", res[i]);
}
return 0;
}
时间复杂度O ( m ) O(m)O(m)，空间O ( n + m ) O(n+m)O(n+m)。