# 332. Reconstruct Itinerary

• Time: $O(|E|\log |E|)$
• Space: $O(|E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: vector findItinerary(vector>& tickets) { vector ans; unordered_map> graph; for (const vector& ticket : tickets) graph[ticket[0]].insert(ticket[1]); dfs(graph, "JFK", ans); reverse(ans.begin(), ans.end()); return ans; } private: void dfs(unordered_map>& graph, const string& u, vector& ans) { while (graph.count(u) && !graph[u].empty()) { const string v = *graph[u].begin(); graph[u].erase(graph[u].begin()); dfs(graph, v, ans); } ans.push_back(u); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public List findItinerary(List> tickets) { LinkedList ans = new LinkedList<>(); Map> graph = new HashMap<>(); for (final List ticket : tickets) { graph.putIfAbsent(ticket.get(0), new PriorityQueue<>()); graph.get(ticket.get(0)).offer(ticket.get(1)); } dfs(graph, "JFK", ans); return ans; } private void dfs(Map> graph, final String u, LinkedList ans) { final Queue arrivals = graph.get(u); while (arrivals != null && !arrivals.isEmpty()) dfs(graph, arrivals.poll(), ans); ans.addFirst(u); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: ans = [] graph = collections.defaultdict(list) for a, b in reversed(sorted(tickets)): graph[a].append(b) def dfs(u: str) -> None: while u in graph and graph[u]: dfs(graph[u].pop()) ans.append(u) dfs('JFK') return ans[::-1]