欧拉路径，排列单词

Question

每扇门上都有许多磁性板。每块板上都写了一个单词。这些板必须按照一定的顺序排列，使得每个单词的首字母与前一个单词的尾字母相同。例如，单词“acm”可以跟随单词“motorola”。

示例： skenzo logicboxes orderbox

答案：可以排序

我知道这个问题涉及欧拉路径。但是我无法实现它。有人能告诉我如何实现它吗？意思是我该如何制作图形，并连接哪些节点。我知道我必须使用邻接矩阵，但必须连接哪些节点。

- dejavu

---

如果答案不令人满意或不正确，为什么我要接受它呢？ - dejavu

我并不是建议你接受不令人满意或不正确的答案。当我写下那个评论时，你有10个问题，其中8个有答案，但没有被采纳。这往往会让人们对你的新问题回答产生厌倦。我看到你现在已经采纳了一些答案，这对你（有一点声望提升）和社区（可以看到哪些答案有效）都有帮助。 - Ted Hopp

是的，SPOJ问题..但很有趣。 - dejavu

也许我漏掉了什么，但你是不是在寻找一个哈密顿路径（每个单词恰好访问一次），而不是欧拉路径（每条边恰好访问一次）？ - templatetypedef

取决于你所称之为的边缘和节点。例如，如果每个字母有一个节点，则单词集合就是边缘集合。或者，将单词视为节点，并为每个单词从其结尾字母到其他单词的匹配起始字母添加边缘。 - James Waldby - jwpat7

Answer 1

WORDS1，如果我没记错的话。与其他一些人不同，我认为你想要的是欧拉路径，而不是哈密顿路径。在结果图中，单词是边（从第一个字母到最后一个字母），而字母（方便起见，只有ASCII中的小写字母'a'到'z'）是顶点。

实际上，你所需要的并不是路径本身，而是要知道是否存在这样的路径。因此，你需要了解图存在欧拉路径的必要和充分条件。

显然，要存在这样的路径，图必须是连通的。你可以用并查集有效地确定这一点。
然后，这样的路径的存在会对顶点的入度和出度施加条件。如果你正确地表述这些条件，a) 它们是必要且充分的，b) 它们易于检查。

找到这些条件自己更有趣，但你也可以在维基百科关于欧拉路径的文章中找到它们。

- Daniel Fischer

---

我无法理解为什么字母应该是顶点。你能给一个小例子吗？虽然程序有解决方案，但我不知道为什么这个概念无法理解。我的想法是，假设单词是“acm”，另一个单词是“moto”，那么acm与moto在有向图中相连。请问您能否澄清一下？ - dejavu

每个单词都是从第一个字母到最后一个字母的边，例如recent~>(r->t)，radar~>(r->r)。因此，您可以从一个具有26个顶点和没有边的图开始，随着边的出现而添加边。当所有边都记录完毕后，您需要丢弃所有没有关联边的顶点。这就是您需要研究的图形。 - Daniel Fischer

图应该是有向的还是无向的？ - gsdf

@SurayansTiwari 指定。每个单词都是从它的第一个字母到最后一个字母的边缘。 - Daniel Fischer

Answer 2

可以使用第一个和最后一个符号的ASCII码作为图形顶点。您可以尝试使用DFS进行顶点排序，然后检查是否对所有顶点进行了排序。如果是，则所有单词都可以按照该顺序排列。

- andigor