題目

Given a list of airline tickets rePResented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK. Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”]. All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

解題

題目大意是找一條路徑，可以從頭到尾的羅列出每個航站。其實就是一個有向圖，然后一筆畫畫完所有的點，按順序列出所有的點。也就是歐拉路徑的定義。 首先題目定義，必然存在一條歐拉路徑，且每個點有多個路徑按字典序排序。首先采用dfs尋找字典序最小的一條路徑，直到某點阻塞，不能通往新的點，那么這一點必然是歐拉路徑的終點。也就得到了一條從起點到終點的路徑L。 對于路徑中的其它點，只能和路徑組成環，在dfs遞歸回退的過程中，每一點繼續dfs遍歷，最終會阻塞在L上，并組成一個環，回退該路徑并記錄即可。相當于在每個點尋找到L的路徑，并將其并回L。同時遞推回歸的過程中，先回歸的點在路徑的后面，所以要逆著記錄進鏈表。