欧拉回路

你说得对但我又开了一个坑，气笑了。

---

定义

存在一条图上的路径，经过所有边，则我们将该路径称为欧拉路径。

如果一条欧拉路径是回路，我们叫其欧拉回路。

存在欧拉回路的图为欧拉图。

性质

以下三条性质互相等价。

• 图 $G$ 为欧拉图；
• 若图 $G$ 为无向图，所有点的度数均为偶数，否则每个顶点的入度与出度相等；
• 图 $G$ 可被分解为若干条不共边的环。

另外，一个图存在欧拉路径当且仅当刚好有 $2$ 个点的度数为奇数（其实全偶形成的欧拉回路也算欧拉路径）。

求解

下述 Hierholzer 算法，核心原理是利用上面的环分解性质，