欧拉图
2026-04-08
基础概念
欧拉路径:从某个点出发,经过所有边一次。
欧拉回路:从某个点出发,经过所有边一次,回到这个点。
对于一个联通的无向图的欧拉路径,若起点与终点不同,则它们都应该是奇数度的,其他点必须是偶数度;如果起点终点相同,则所有点都是偶数点。
因此,一个联通的无向图中存在欧拉路径的充要条件是仅有 0 或 2 个奇数点。
同理,一个联通的无向图中存在欧拉回路的充要条件是没有奇数点。
证明
考虑构造一个 DFS。
由于除了起点终点以外其余点一定是偶数点,那么从起点出发,每个点一定在进去以后可以出来,具体路径类似于一条边后有几个相邻的环(共用某几个点,且不一定绕圈,可以来回走),在进入终点后出不来(起点终点重合则此时出去后一定要回来)。
换句话说,我们可以先找到从起点到终点的最短路后每次加环,便可以构造出合法方案。
对于一个联通的有向图的欧拉路径,若起点与终点不同,则起点出度比入度大 1,终点入度比出度大 1,其余点出度等于入度;若起点与终点相同,则所有点的入度应等于出度。
同理,一个联通的有向图中存在欧拉回路的充要条件是所有点出度等于入度。
细节
上面所述的 DFS 做法最优显然是 O(n+m) 的,但如果一个点有多个自环,最差会退化成 O(m2),需要进行一些优化。
具体的,我们可以在走过一条边的时候不只是把它标记,而是直接把它删掉(无向图记得把它的反向边一起删了)。
重要
在未经优化的 DFS 中,如果遇到一个点多次自环,容易发现递归过程中是 O(m2) 的复杂度。
具体解决方法是将点 u 的遍历改为 for(int &i = h[u] ; ~i ; ),并且在接下来 continue 和向下递归的时候注意添加 i=ne[i],能够避免当前节点以上的祖先节点按照原顺序再跑一遍。
例题
Acwing 1123. 铲雪车
读完题,我们会发现任意一段路径的两端的点入度和出度都会加 1,也就是说整个图的点的度数都是偶数,由于扫雪车最开始一定位于道路上,所以我们一定可以找到一个欧拉回路。
此时,答案其实是 20km/hsum(其中 sum 是路径长度和),压根不是图论问题。
Acwing 1184. 欧拉回路
一道模板题,根据上述细节进行处理即可。
AcWing 1124. 骑马修栅栏
由于需要求字典序最小的方案,对于一个普通的 DFS,显然可以走每个边时选择最小的,但对于我们在 DFS 最后加入 u,而答案又是逆序的成立吗?
显然是成立的,因为我们如果选择了当前 u 连边的最小点,则其他点也一定会从它出发被经过,所以最小点会被放到答案序列的最后,也就是逆序的最前端。
因此,我们只需要每次选择最小的连点进行 DFS 即可。
AcWing 1185. 单词游戏
对于每个单词的首字母 s 和末字母 t,这个单词其实相当于一条从 s 到 t 的边,题目要求的也就是是否存在欧拉路径。
另外,由于只需要是否存在欧拉路径,我们可以使用并查集判断连通性,再看除起点终点是否有奇数度的点即可。
