我一直在用 codility.com 问题进行培训。Eta 2011 有一个问题，它试图找到唯一哈密顿路径的数量。你可以在这里阅读整个问题
总之。我们有一个图，其中每个内部节点恰好连接到 3 个其他节点，而外部节点连接到 1 个内部节点。我们绘制一条通过所有外部节点的路径。现在所有节点（内部和外部）都连接到正好 3 个节点。这是一个无向图。
他想在 O(N) 内解决问题！！！可用的解决方案可以解决 O(2^N) 或更高的问题。也有启发式解决方案，但显然它们并不精确。使用图中每个节点都连接到其他三个节点的知识，是否有可能在 O(N) 中求解哈密顿路径？
由于版权，我相信我无权复制/粘贴整个问题。但在第一段中提供了一个链接。
欢呼莫阿塔兹
该图基本上是一棵树，其根节点具有 3 个子节点，所有其他非叶节点具有 2 个子节点。叶子从左到右连接。
您可以将每个子树视为具有两个端点叶节点（例如开始和结束）。
现在给定一个以节点 n 为根的子树。如果 hamiltonian 路由不涉及 n 并且它是 parent，那么它将涉及从开始到结束的路径，并将覆盖子树的所有顶点（实际上，在 n 处路由的子树中的 hamiltion 路由）。
现在考虑树的根。假设我们对 x 和 y 取边，其中 x 位于左侧，y 位于右侧。
现在我们必须在 x 处取从根到子树终点的路径，以及在 y 处子树起点的路径。
（一个数字有帮助）。
路径的其余部分通过将需要路径的子树的开始连接到结束来完成。
这给出了一个递归算法，我相信可以在 O(n) 时间内计算出来。
30分钟的疯狂期望。
Hamiltonian cycle是图的某些子集的多项式，例如co-comparability 图。
如果您的输入图是此类图之一，您可以在多项式时间内解决问题。请注意，我并不是说哈密顿循环不是NP-C。我所说的只是某些图的多项式。
因此，如果您的输入图是一个可比性图，那么您就有一个多项式解决方案。
首先，考虑一棵树，其根和所有非叶节点都有两个孩子。叶子也是从左到右连接的，但是第一片叶子没有和最后一片叶子相连。从最左边到最右边的叶子有多少条路径？
答案只有一个，不难证明。
现在从输入中取出树。选择任何节点并删除其边缘之一。剩下的两棵树的结构与我在开头提到的那棵树相同。使用这两个，您可以准确地构建一条哈密顿路径。
现在您选择的节点有三个可以删除的边，因此总共有三种方法可以制作哈密顿路径:)。
因此代码归结为检查一致性并编写 3 以防万一一切正常。30分钟真的没有那么疯狂。