大数学家欧拉一生中的大部分时间在俄国和普鲁士度过。1735年，他提出了著名的柯尼斯堡七桥（Seven Bridges of Königsberg）问题：

柯尼斯堡（今俄罗斯加里宁格勒）的市区横跨普雷格尔河两岸，河中心有两个小岛，小岛与河的两岸有七座桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？

当时欧拉并没有找到这个问题的解。第二年，他证明了不存在符合条件的走法。在论文中，欧拉将柯尼斯堡的实际情况抽象成了二维空间上点与线的组合，桥可以视为线（边），桥连接的陆地视为点（顶点）——这就是数学中图论思维的起源。

如上，柯尼斯堡七桥问题就被推广为“一笔画”问题：

对于一个给定的图，怎样判断是否存在一个恰好包含了所有的边，并且没有重复边的路径？

背景铺垫完了，下面介绍相关的概念和定理。

在图论中：

如下gif所示的图就是欧拉图，存在一个欧拉路径。

下图是一笔画成的“串”字，也就是说烧烤店门口挂的这个字可以用单条LED灯带做成。

那么柯尼斯堡七桥问题为什么不能“一笔画”呢？来看看欧拉提出的定理。

欧拉同时考虑到了有向图与无向图的情况，因此要分别讨论。

定理：

连通无向图G有欧拉路径的充要条件为：G中奇度顶点（即与其相连的边数目为奇数的顶点）有0个或者2个。

证明：

必要性 如果图能够被一笔画成，那么对每个顶点，考虑路径中“进入”它的边数与“离开”它的边数［注意前提是无向图，所以我们不能称其为“入边”和“出边”］。很显然这两个值要么相同（说明该顶点度数为偶），要么相差1（说明该顶点度数为奇）。 也就是说，如果欧拉路径不是回路，奇度顶点就有2个，即路径的起点和终点；如果是欧拉回路，起点与终点重合，则不存在奇度顶点。必要性得证。

充分性

可知，柯尼斯堡七桥问题中的图有4个奇度顶点（1个度数为5，3个度数为3），所以不存在欧拉路径。

定理：

底图连通的有向图G有欧拉路径的充要条件为：G的所有顶点入度和出度都相等；或者只有两个顶点的入度和出度不相等，且其中一个顶点的出度与入度之差为1，另一个顶点的入度与出度之差为1。

显然，可以通过与无向图情况相似的思路来证明，过程略去。

欧拉定理介绍完了，那么如何找到具体的路径呢？

首先，我们当然要判断图的连通性，非连通图是不存在欧拉路径/回路的。判断图的连通性可以通过传统的DFS和BFS方法，也可以通过之前讲过的并查集实现，另外还有基于传递闭包的Floyd-Warshall算法（没错就是求最短路的那个），不再赘述。

如果图是连通的，我们再遍历每个顶点的度（有向图就是入度和出度），根据欧拉定理即可轻松地判断图中是否欧拉路径/回路。如果是欧拉路径的话，还能顺便找出路径的起点和终点。

接下来，我们通过俗称“套圈法”的DFS思路来寻找欧拉路径/回路。

参考欧拉定理充分性的证明过程，欧拉图可以分割为多个相交的回路，所以我们可以从起点开始，通过DFS逐渐扩展路径，并标记边已经被遍历过（根据定义，已经被标记了的边之后就不会再走），直到形成一个回路。然后回溯到上一个有边没被遍历到的顶点——就是上文说的“c0和图的剩余部分必然存在某公共顶点v1”，以它为起点重复同样的操作，直到所有回路都被找出来。在回溯阶段所记录的路径就是所求的欧拉路径/回路。

听起来似乎有些混乱，来看一道例题吧。

传送门见这里。

题目大意：给定N个单词，要求把这些单词不重复地排成一个序列，使每个单词的首字母与前一个单词的末尾字母相同（e.g. aloha.aloha.arachnid.dog.gopher.rat.tiger），以点号分隔输出。如果存在不止一个解，输出字典序最小的那个序列。如果没有解，输出三个星号。

我们可以将每个单词的两端视为顶点，单词本身视为有向边，就能构造出有向图。先判断连通性，再判断是否存在欧拉路径/回路（同时找出起点），最后用套圈法找出具体的路径——由于DFS回溯得到的路径是倒序的，所以把它们放在栈中记录比较方便。

本题需要特别注意的点在于输出字典序最小的那个序列，因此先要将所有单词按字典序排序。另外，如果存在的是欧拉回路，那么得选择字典序最小的单词作为起点。

今天时间不太够了，AC代码之后再补上，看官可参考其他大佬的代码，或移步Discuss区。

寻找欧拉路径/回路也可以使用Fleury算法，但是它要额外检测图中的桥边，相比DFS而言不太容易操作。看官可以参考图论或离散数学教材获取更多细节。

民那晚安。