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”]. Example 2: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] Return [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]. Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

s思路: 1. 給兩兩連接的機場，要求得到一整條路線。仔細觀察，還是圖的遍歷嘛，但又不同與之前看到的圖的遍歷，因為之前的遍歷是考慮節點是否被訪問，而這里則是邊是否被訪問。這一點一定要先搞明白。如下圖，從JFK開始，有兩個鄰居，ATL和SFO,先訪問哪個題目有規定，字典排序小的機場先訪問，所以先訪問ATL,由于是找路線，自然是用dfs最方便，訪問了ATL，常規的做法是需要標記已經訪問過，但這里只需要使用一次這條邊，所以干脆直接刪除這條邊，就不用標記是否訪問，然后到ATL繼續遍歷，發現也有兩個鄰居JFK,SFO，這里也是一樣，西安訪問JFK,同時把JFK這條邊刪除；現在到JFK后，發現JFK只有一個鄰居SFO（ATL已經被刪除），于是訪問SFO,同時刪除SFO這條鏈接；繼續遍歷SFO的鄰居，發現有ATL,于是訪問ATL,同時刪除ATL這條邊，現在到ATL發現也只有一個鄰居SFO,于是繼續訪問SFO,同時刪除鏈接，到SFO發現沒有鄰居了，意味著結束了嗎？還是需要回到上一層繼續遍歷呢？保險起見，是需要回到上一層吧！ 2.由于要字典順序訪問，所以最好對每個節點的鄰居排序，所以不用vector放鄰居，而用map. 3. 上面分析還是不對，debug的時候，發現前面分析的不對呀，沒有反應過來，所謂圖里面元素的排序，本質就是topological sort,先用dfs走一邊，誰的鄰居節點都遍歷完誰就先放入vector，最好等所有節點都放入vector再reverse vector即可！由于不是檢測是否有環，所以仍然不需要用visited來表示一個節點是否訪問完全還是正在訪問，