2.9 如何从给定的车票中找出旅程路线

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）。那么可以得到旅程路线为：北京->上海，上海->大连，大连->西安，西安->成都。假定给定的车票不会有环，也就是说有一个城市只作为终点而不会作为起点。

分析与解答：

对于这种题目，一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种方法的效率不高，它的时间复杂度为O(n)。这里重点介绍另外一种更加简单的方法：hash法。主要的思路为根据车票信息构建一个map，然后从这个map中找到整个旅程的起点，接着就可以从起点出发依次找到下一站，进而知道终点。具体的实现思路为：

（1）根据车票的出发地与目的地构建map。

Tickets={（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）}

（2）构建Tickets的逆向map如下（将旅程的起始点反向）：

ReverseTickets={（“成都”到“西安”），（“上海”到“北京”），（“西安”到“大连”）， （“大连”到“上海”）}

（3）遍历Tickets，对于遍历到的key值，判断这个值是否在ReverseTickets中的key中存在，如果不存在，那么说明遍历到的Tickets中的key值就是旅途的起点。例如：“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起点。实现代码如下：

程序的运行结果为

算法性能分析：

这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。