LeetCode Reconstruct Itinerary 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:

1. 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"].
2. All airports are represented by three capital letters (IATA code).
3. 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.

---

给定一系列机票，每张机票标明了A→B的一段旅程，现在要求把所有的机票旅程连成一条完整的长距离航线，要求起点是JFK。如果有多条合法的航线，则输出字典序最小的那条。 显然要转换为图的问题，每个机场转换为一个点，每张机票转换为一条边，然后从JFK开始DFS，保留每条合法的航线，然后sort取字典序最小的航线。 把问题转换为图不难，使用hash给每个机场编号，然后新建一个图。在图中以JFK开始DFS也不难，每深入DFS一层，机票数目减1，当机票数目为0时，DFS结束，找到一条合法航线。 我一开始是这么做的，但是TLE了，因为这样可能会进行很多次DFS， 找到多条航线，还需要sort取字典序最小的航线。 有没有办法一次找到字典序最小的航线呢，只需要在DFS的时候，每次都从字典序最小的机场开始下一层DFS，这样第一次DFS成功的航线肯定是字典序最小的航线。 所以我们给机场编号的时候，先使用map记录，map会自动按key的字典序从小到大排好。然后遍历map重新编号，并且用hash2记录编号和机场的对应关系。这样，在DFS的时候，从0→n的遍历，就自动是按字典序从小到大遍历。 代码如下： [cpp] class Solution { private: bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) { if (lines == 0) return true; int n = hash2.size(); for (int i = 0; i < n; ++i) { // 字典序从小到大深搜 if (graph[start][i] > 0) { –graph[start][i]; ans += hash2[i]; if (dfs(ans, hash2, graph, i, lines – 1))return true; ++graph[start][i]; ans = ans.substr(0, ans.size() – 3); } } return false; } public: vector<string> findItinerary(vector<pair<string, string>> tickets) { map<string, int> hash1; vector<string> hash2; int cnt = 0, n = tickets.size(); for (int i = 0; i < tickets.size(); ++i) { // 记录 hash1[tickets[i].first] = 0; hash1[tickets[i].second] = 0; } for (auto it = hash1.begin(); it != hash1.end(); ++it) { it->second = cnt++; // 字典序从小到大编号 hash2.push_back(it->first); } vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图 for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]]; int start = hash1["JFK"]; string ans = "JFK"; dfs(ans, hash2, graph, start, n); // 深搜 vector<string> Itinerary; for (int i = 0; i <= ans.size() – 3; i += 3)Itinerary.push_back(ans.substr(i, 3)); return Itinerary; } }; [/cpp] 本代码提交AC，用时22MS。]]>