c++ - 检查是否可以链接字符串列表

Question

问题

实现一个功能bool chainable(vector<string> v) , 它以一组字符串作为参数并返回 true如果它们可以被链接。如果第一个字符串以第二个开头的相同字符结尾，则可以链接两个字符串，例如:

ship->petal->lion->nick  = true;  (original input is list not LL)
ship->petal   axe->elf   = false;

我的解决方案:

我的逻辑是，如果它是可链接的，则只有一个开始和结束不匹配。所以我创建了一个开始列表和一个结束列表。像这样。

starts:s,p,l,n
ends:  p,l,n,k

如果我删除公共(public)元素，则列表最多应包含一项。即s和k。如果是这样，该列表是可链接的。如果列表是循环的，则最终列表为空。

但我想我在这里遗漏了一些案例，

编辑:好吧，很明显我的解决方案有问题。我们可以为此得出最佳算法吗？

Answer 1

问题是检查一个Eulerian path存在于有向图中，其顶点是作为至少一个提供的单词的第一个或最后一个字母出现的字母，其边是提供的单词(每个单词是从第一个字母到最后一个字母的边)。

此类图中存在欧拉路径的一些必要条件:

1. 图必须是连通的。
2. 所有最多有两个异常(exception)的顶点有同样多的入边和出边。如果存在异常顶点，则恰好有两个，其中一个出边比入边多一条，另一个入边比出边多一条。

必要性很容易看出:如果一个图有欧拉路径，那么任何这样的路径都会遇到除孤立顶点之外的所有顶点(既不是传出边也不是传入边)。通过构造，这里考虑的图中没有孤立的顶点。在欧拉路径中，每次访问一个顶点时，除了开始和结束之外，使用一条入边和一条出边，因此除了起始和结束顶点之外的每个顶点都有相同数量的入边和出边。起始顶点的出边比入边多一条，结束顶点的入边比出边多一条，除非欧拉路径是一个循环，在这种情况下所有顶点的入边和出边的数量相同。

现在重要的是这些条件也足够。可以通过对边的数量进行归纳来证明这一点。

这样可以进行非常有效的检查:

• 记录从单词中获得的所有边和顶点
• 使用 union 查找结构/算法来计算图的连通分量
• 记录所有顶点的入度-出度

如果 number of components > 1 或有(至少)一个顶点 |indegree - outdegree| > 1 或有两个以上的顶点 indegree != outdegree，单词不可链接，否则为。