Problem

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:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

问题描述

给定一列机票，每张机票上有起飞机场和到达机场 (每个机场都用三个字母表示)，有一个人从 JFK 起飞，返回一个机场列表代表这个人飞行的计划，题目确保一定有至少一个合法的计划，如果有多个计划，则返回字母序最小的。

样例

输入: [['JFK', 'SFO'], ['JFK', 'ATL'], ['SFO', 'ATL'], ['ATL', 'JFK'], ['ATL', 'SFO']]
输出: ['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']
解释: 有两个合法的计划
['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']
['JFK', 'SFO', 'ATL', 'JFK', 'ATL', 'SFO']
返回字母序最小的即可

解法 1

这道题是典型的「有向图欧拉路径」问题，可以通过深度优先遍历解决。

由于题目中说明了这样的路径一定存在，所以我们不需要判断图中是否存在这样的路径。并且图中给定了出发点，那么只需要从出发点开始进行深度优先遍历即可。题目中要求返回一个字典序最小的合法计划，那么我们每次在选择下一个访问的结点时，选择字典序最小的结点。

故我们在构造图时，我们要将每个结点指向的所有结点按照字典顺序排序，这可以用队列来实现。然后我们依次对这些结点做深度优先遍历，并将这些结点在图中移除，再将结果添加到 res 中，最后返回 res 的逆序即可。

参考代码:

import bisect

class Solution:
    def find_itinerary(self, tickets):
        graph = collections.defaultdict(collections.deque)
        res = collections.deque()
        for from_city, to_city in tickets:
            bisect.insort(graph[from_city], to_city)
        
        def dfs(from_city):
            while from_city in graph and len(graph[from_city]) > 0:
                dfs(table[from_city].popleft())
            res.appendleft(from_city)
            
        dfs("JFK")
        return list(res)