# Question

Formatted question description: https://leetcode.ca/all/332.html

 332	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:

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:

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.

@tag-graph


# Algorithm

First of all, the graph is established, through the adjacency linked list.

Since the problem requires the solution to be small in alphabetical order, then we consider using multiset, which can be automatically sorted.

After our graph is built, we start traversal from node JFK. As long as there is a node in the multiset mapped by the current node, we take this node out, delete it in the multiset, and then continue to recursively traverse this node.

Finally, the order of our results is the opposite of what we need, we will flip it again at the end。

# Code

Java

// Java Lambda
public List<String> findItinerary(String[][] tickets) {
Map<String, PriorityQueue<String>> targets = new HashMap<>();
for (String[] ticket : tickets)
visit("JFK");
return route;
}

Map<String, PriorityQueue<String>> targets = new HashMap<>();