数据结构与算法

一笔画问题：给定一个 n 个点 m 条边的图，要求从指定的顶点出发，经过所有的边恰好一次。

定义：

定义：

如果没有保证至少存在一种合理的路径，我们需要判别这张图是否是欧拉图或者半欧拉图，具体地：

从上述描述中可知，如果图 G 是一个连通图，则可用如下表格判断其是否是欧拉图 / 半欧拉图：

332: 重新安排行程 - 力扣 https://leetcode-cn.com/problems/reconstruct-itinerary/

将该题转化为一笔画问题：给定一个 n 个点 m 条边的图，要求从指定的顶点出发，经过所有的边恰好一次，且使得路径的字典序最小。

Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：

当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。

不妨倒过来思考。我们注意到只有那个入度与出度差为 1 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈）。

对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。

这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。

另外，为了保证我们能够快速找到当前节点所连的节点中字典序最小的那一个，我们可以使用优先队列存储当前节点所连到的点，每次我们 O(1) 地找到最小字典序的节点，并 O(logm) 地删除它。

C++ 代码实现如下：

753: 破解保险箱 - 力扣 https://leetcode-cn.com/problems/cracking-the-safe/

题目描述：

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

这道题说的是给了 k 个数字，值为 0 到 k-1，让我们组成 n 位密码。我们可以发现，为了尽可能的使钥匙串变短，所以我们的密码之间尽可能要相互重叠：

我们可以发现，两个长度为 n 的密码最好能共享 n-1 个数字，这样累加出来的钥匙串肯定是最短的。

密码共有 n 位，每一个位可以有 k 个数字，那么总共不同的密码总数就有 kn 个，而每个密码可以公用 n - 1 位，所以破解保险箱的密码最短长度为：n - 1 + kn 位。

我们可以考虑创建一个有 kn-1 个节点的图，每个节点有 k 条出边，则该图中一共有 kn 条边，将【节点代表的 n - 1 位数字 + 边代表的 1 位数字】作为经过该条边后尝试的密码值，而经过边后到达的新节点代表的 n - 1 位数字，可以作为下一个密码的前 n - 1 位数字使用，这样可以保证每个密码值不重复，又完全覆盖了 kn 个密码值。

以三位密码的二进制保险箱（n = 3, k = 2）举例：

我们可以按如下顺序遍历图中所有的边：

最后可得出破解该保险箱的最短字符顺序为：0011101000，其位数也正好为 n - 1 + kn = 3 - 1 + 23 = 10 位。

将其拓展为 n 位 k 个数字的密码：比如节点为 a1a2a3...an 经过边 am 后的新节点为 a2a3...anam。

仍利用 Hierholzer 算法：