欧拉道路与欧拉回路

· · 个人记录

别问为什么是欧拉道路不是欧拉通路

定义

注：如果图不连通，以下判定均不成立，以下内容以图是联通的为前提。

欧拉道路：一个图中的一条路径，使得每条边只经过一次（注意不是点）。

判定：

  1. 无向图：所有度数为奇数的点只有0或2个；
  2. 有向图：所有点中，有且仅有一个点的出度比入度多1，有且仅有一个点的入度比出度多1（前者是欧拉道路的起点，后者是欧拉道路的终点），其它点出、入度均相等。

欧拉回路：一个图中的一条欧拉道路，且起点和终点是一条边。

判定：

  1. 无向图：所有点的度数均为偶数；
  2. 有向图：所有点的出度均等于入度。

在欧拉回路中，可以选择任意一个点作为起点，因为它是一个回路。

欧拉图：有欧拉回路的图；

半欧拉图：只有欧拉道路没有欧拉回路的图。

求解

假设一个无向图G是半欧拉图。

首先找到任意一个度数为奇数的点（只有两个），以它作为起点进行DFS；遇到没有访问过的边，将其记录为e并删除（注意要真正地删除，而不是简单地标记，这样才能使复杂度降低到O(N+M)，因为即使打上了标记也还是会遍历到，只是不会递归而已），然后递归它另一端的点，最后将该点加入答案栈中。

如果无向图G是欧拉图，随便找一个点开始DFS即可。

对于有向图中的欧拉道路，需要找到出度比入度多1的点作为起点DFS；而对于有向图的欧拉回路，随意找一个点开始DFS即可。

需要注意的是，如果图不保证联通，我们还需要判断图是否联通。可以以任意一个度不为0的点开始DFS，如果答案路径中的边数小于总边数，那么该图就不是连通图，也就不是欧拉图或半欧拉图。

例题

here

使用邻接表存图求解欧拉路问题时，需要注意几个细节：

  1. while (~h[u])不能写成for (int i=h[u];~i;i=ne[i])，这样即使后面遍历到的点已经将ne[i]删除了，也就是此时h[u]已经等于-1了，后者还会错误地继续循环，使时间复杂度退化成O(NM)。

  2. 已经删除了边之后还会遍历到vis[u]=1的边是因为我们打标记时是给无向边的两条双向边同时打的，删除了一条还有另外一条。