检查是否字符串列表可以链接 [英] Checking if a list of strings can be chained

问题描述

问题

实现一个功能布尔链式（矢量＆lt;串＆GT; 5），这需要一组字符串作为参数，并返回真如果能链。

Implement a function bool chainable(vector<string> v), which takes a set of strings as parameters and returns true if they can be chained. Two strings can be chained if the first one ends with the same character the second starts with, e.g.:

ship->petal->lion->nick  = true;
ship->petal   axe->elf   = false;

我的解决方法：

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

My logic is that if its chainable there will only be one start and end that don't match. So I create a list of starts and a list of ends. like so.

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

如果我删除了共同的元素，该清单应包含最多一个项目。即S和ķ。如果是这样的列表是可链接。如果列表环状的，最终的列表是空的。

if I remove the common elements, the lists should contain at most one items. namely s and k. If so the list is chainable. If the list is cyclic, the final lists are empty.

但我认为我缺少某些情况下在这里，

But i think I am missing some cases here,

编辑： 好吧我清楚我的解决方案有缺陷。我们可以断定这个最好的算法？

Okay clearly I had faults in my solution. Can we conclude the best algorithm for this ?

推荐答案

现在的问题是要检查是否一笔画问题存在于向图的顶点使用的字母出现作为至少一个的供给字和第一或最后一个字母，其边缘是所提供的字（1个字是从它的第一个字母，以它的前边缘）。

The problem is to check if a Eulerian path exists in the directed graph whose vertices are the letters occurring as first or last letter of at least one of the supplied words and whose edges are the supplied words (each word is the edge from its first letter to its last).

为欧拉路径在这样的图表中存在的一些必要条件：

Some necessary conditions for the existence of Eulerian paths in such graphs:

1. 该图必须连接。
2. 所有顶点至多两个例外有一样多的传入和传出的边缘。如果特殊的顶点存在，恰好有二，其中一人有一个比较外向的边缘比进来的，其他有比外向多了一个进入的边缘。

的必要性是很容易看到：如果有图有欧拉路径，任何这样的路径符合除孤立顶点（没有传出，也没有入边）的所有顶点。通过构造，没有孤立顶点在审议该图在这里。在一个欧拉路径，每次一个顶点被访问，除了开始和结束，一个输入边和一个输出边使用，所以每个顶点与起始的可能的例外和结束顶点有一样多的传入和传出边缘。起始顶点具有一个多出边比传入和结束顶点比传出多一个引入边除非欧拉路径是一个周期，在这种情况下，所有顶点具有一样多的传入和传出边缘

The necessity is easily seen: If a graph has Eulerian paths, any such path meets all vertices except the isolated vertices (neither outgoing nor incoming edges). By construction, there are no isolated vertices in the graph under consideration here. In a Eulerian path, every time a vertex is visited, except the start and end, one incoming edge and one outgoing edge is used, so each vertex with the possible exception of the starting and ending vertex has equally many incoming and outgoing edges. The starting vertex has one more outgoing edge than incoming and the ending vertex one more incoming edge than outgoing unless the Eulerian path is a cycle, in which case all vertices have equally many incoming and outgoing edges.

现在最重要的事情是，这些条件也足以的。人能证明通过感应上的边的数量。

Now the important thing is that these conditions are also sufficient. One can prove that by induction on the number of edges.

这允许一个非常有效的检查：

That allows for a very efficient check:

• 记录所有的边缘，自言为获得顶点
• 使用联合查找结构/算法来计算图的连接组件
• 记录入度 - 出度所有顶点

• record all edges and vertices as obtained from the words
• use a union find structure/algorithm to count the connected components of the graph
• record indegree - outdegree for all vertices

如果若干组件的制造＆gt; 1 或有（至少）一个顶点与 |入度 - 出度| ＆GT; 1 或有两个以上的顶点入度！=出度的话是不是可链接，否则他们是。

If number of components > 1 or there is (at least) one vertex with |indegree - outdegree| > 1 or there are more than two vertices with indegree != outdegree, the words are not chainable, otherwise they are.

这篇关于检查是否字符串列表可以链接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！