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.
idea:
we have a list of edges, each node pair represents for [from, to]. and that are the series of tickets
and we know that the journel starts with JFK, we need to resort it and return with the nodes in order.
example:
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.
there are four instructions:
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.
4 One must use all the tickets once and only once.

public List<String> findItinerary(List<List<String>> tickets)

I’m still trying to solve this using BFS, each time I only choose one neighbor to go, the one with smallest lexi order. so it’s bascally dfs but I’m too lazy to even think about how to write this in dfs.
but sadly, it’s MLE

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        HashMap<String, List<String>> map = new HashMap<>();
        
        for (List<String> ticket: tickets) {
            map.computeIfAbsent(ticket.get(0), k -> new ArrayList<>());
            map.get(ticket.get(0)).add(ticket.get(1));
        }
        // we will using bfs but each time we only go with negihbor with minimum lexi， although for situations like this, it's better for us to implement dfs instead of bfs
        Queue<String> queue = new LinkedList<>();
        queue.offer("JFK");
        List<String> res = new ArrayList<>();
        res.add("JFK");
        //i don;t think visited will be useful, because we might revisited previous node, like we might need to return the JFK again in example
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            if (!map.containsKey(cur)) { //we neeed to check if map contains this key in case it is the last one
                break;
            }
            int size = map.get(cur).size();
            String min = "ZZZ";
            for (int i = 0; i < size; i++) {
                if (map.get(cur).get(i).compareTo(min) < 0) {
                    min = map.get(cur).get(i);
                }
            }
            queue.offer(min);
            res.add(min);
        }
        return res;
    }
}

So we using DFS:
/ / why can DFS guarantee to travel all the edges and only once?

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        
        for (List<String> ticket: tickets) {
            map.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
        }
        List<String> route = new LinkedList<>();
        dfs(map, route, "JFK"); 
        return route;
    }
    
    private void dfs(HashMap<String, PriorityQueue<String>> map, List<String> route, String node) {
        while (map.containsKey(node) && !map.get(node).isEmpty()) { //if we can move forward 
            dfs(map, route, map.get(node).poll());
        }
        route.add(0, node); //alwatys added to the head of this route list
    }
}

Of course, we can write DFs in an iterative way

public List<String> findItinerary(String[][] tickets) {
    Map<String, PriorityQueue<String>> targets = new HashMap<>();
    for (String[] ticket : tickets)
        targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
    List<String> route = new LinkedList();
    Stack<String> stack = new Stack<>();
    stack.push("JFK");
    while (!stack.empty()) {
        while (targets.containsKey(stack.peek()) && !targets.get(stack.peek()).isEmpty())
            stack.push(targets.get(stack.peek()).poll());
        route.add(0, stack.pop());
    }
    return route;
}