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

Question

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

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

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

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

EDIT:好吧，显然我的解决方案有缺陷。我们能得出最佳算法吗？

问题是检查是否欧拉路径 http://en.wikipedia.org/wiki/Eulerian_path存在于有向图中，其顶点是作为至少一个所提供的单词的第一个或最后一个字母出现的字母，其边是所提供的单词（每个单词是从其第一个字母到最后一个字母的边）。

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

1. 图形必须连接起来。
2. 最多有两个例外的所有顶点都具有相同数量的传入和传出边。如果存在异常顶点，则恰好有两个，其中一个比传入多一条出边，另一个比传出多一条传入边。

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

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

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

• 记录从单词中获得的所有边和顶点
• 使用并集查找结构/算法来计算图的连接组件
• record indegree - outdegree对于所有顶点

If number of components > 1或者有（至少）一个顶点|indegree - outdegree| > 1或者有两个以上的顶点indegree != outdegree，这些词是不可链接的，否则就是。