欧拉路径与欧拉回路

之前一直不是很会欧拉图，趁着 NOIP 复习的机会来捋一捋。

定义 ​

通路：图中一条路径。或者更准确地，可以表述为一个序列 $u_1,u_2,\cdots,u_n$，对于所有 $1\le i<n$ 满足 $u_i$ 和 $u_{i+1}$ 之间有边的序列称为一条通路。

回路：满足起点和终点在同一点的通路。

欧拉回路：经过每条边恰好一次的 回路。

欧拉图：具有欧拉回路的图。

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

半欧拉图：具有欧拉路径而没有欧拉回路的图。容易发现，具有欧拉回路则必定具有欧拉路径。

判定 ​

一个图是欧拉图或欧拉路径的必要条件：

• 无向图非零度顶点连通。
• 有向图非零度顶点弱连通。

除满足上述条件外，

• 一个无向图是欧拉图当且仅当：顶点度数均为偶数。
• 一个无向图是半欧拉图当且仅当：恰有 2 个奇数度数节点。
• 一个有向图是欧拉图当且仅当：每一个节点入度等于出度。
• 一个有向图是半欧拉图当且仅当：至多一个顶点满足出度与入度差为 1（若存在则为起点），至多一个顶点满足入度与出度差为 1（若存在则为终点），其余顶点入度等于出度，且存在顶点的入度不等于出度（否则是欧拉图）。

根据定义，一个欧拉图具有欧拉回路，一个欧拉图或半欧拉图具有欧拉通路。

Hierholzer 算法 ​

也被称为逐步插入回路法。

假设现在有一个回路 / 通路，图上有一部分边未经过，该算法通过遍历这些未经过的边来找到一条新的回路 / 通路，并用新回路来代替原来的点。

具体实现上，可以设计一个递归来求解，算法流程如下：

• 尝试对当前通路 / 回路上的一个点 $x$ 进行拓展：
  • 遍历 $x$ 的所有出边，
    • 如果该边没有遍历过，则遍历该边
  • 将 $x$ 加入栈中

从判定时得到的起点开始进行这个算法，最后栈中存放的就是欧拉路径经过的节点（逆序）。

为什么要使用栈呢？如果一个图是半欧拉图，那么从这个点进行拓展可能找不到一个回路，只能找到一个通路（通向终点）。并且至多只有一个出边会出现这样的情况（否则与半欧拉图定义相悖）。

这时候，如果顺序输出，那么答案会先进入这个通路，就走不出来了。

举个例子，假设 $x$ 出边有三个点 $a,b,c$，从 $a$ 和 $c$ 出发能够找到一条回路，而从 $b$ 出发会找到一条通路。

假设此时枚举边的顺序是 $a$ 到 $b$ 到 $c$，那么会先递归进入 $a$，递归这条回路会到达 $x$，这条回路此时没有入栈。递归进入 $b$ 后找到一条通路，只能退出递归，$b$ 通路会入栈。回到 $x$，遍历 $c$ 的回路，这条回路又会到达 $a$。最后 $c$ 的回路先入栈，$a$ 的回路后入栈。这样输出方案的时候，也是 $a$ 到 $c$ 的顺序。

很多题目要求输出字典序最小的路径，只要按照字典序从小到大遍历出边，即可保证得到的是最小字典序（不理解再看一下上面一段）。

常用思路 ​

如果题目要求“恰好一次”，可能是欧拉路径。

记得判定连通性！