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)。