332. Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". 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"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

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

Example 2:

Input: tickets = [["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.

Constraints:

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi and toi consist of uppercase English letters.
• fromi != toi

Solution:

Hierholzer's Algorithm

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
                // 勇于存储最终行程结果的列表
        List<String> result = new LinkedList<>();

        // 使用邻接表表示图，其中键是出发机场，值是按字典顺序排列的到达机场的优先队列
        Map<String, PriorityQueue<String>> graph = new HashMap<>();

        for (List<String> ticket : tickets){
            // ["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]
            String from = ticket.get(0); 
            String to = ticket.get(1);
            // // 如果图中没有出发机场，则创建一个新的优先队列
            graph.computeIfAbsent(from, k -> new PriorityQueue<>()).add(to);
            /*
            graph.computeIfAbsent(from, new Function<String, PriorityQueue<String>>() {
                @Override
                public PriorityQueue<String> apply(String k) {
                    return new PriorityQueue<>();
                }
            }).add(to);
            */
        }

        /*
        MUC, <LHR>
        JFK, <MUC>
        SFO, <SJC>
        LHR, <SFO>
        */


        dfs("JFK", graph, result);
        return result;
    }

    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> result){
        PriorityQueue<String> destinations = graph.get(airport);
        // <MUC> // LHR // SFO // SFC

        while (destinations != null && !destinations.isEmpty()){
            dfs(destinations.poll(), graph, result);
            // dfs(MUC, graph, result);
            // dfs(LHR, graph, result);
            // dfs(SFO, grpah, result);
            // dfs(SFC, graph, result);
        }

        result.add(0, airport); // // 将机场添加到结果列表的前面
        // JKF,MUC,LHR, SFO,SJC
    }
}
// TC: O(nlogn)
// SC: O(m + n)

class Solution {
    Map<String, PriorityQueue<String>> flights;
    LinkedList<String> path;
    Stack<String> sta = new Stack<String>();
    public List<String> findItinerary(List<List<String>> tickets) {
        // create a graph <string, list<string>> to represent the graph
        Map<String, PriorityQueue<String>> flights = new HashMap<>();
        path = new LinkedList<>();
        // starting from "JFK" 
        for(List<String> ticket: tickets) {
            // build the graph here
            // ensure the one that has higher 
            flights.putIfAbsent(ticket.get(0), new PriorityQueue<String>((a, b)->(a.compareTo(b))));
            flights.get(ticket.get(0)).add(ticket.get(1));
        }

        // 难点：是这样的 这是一条能通到底的路， 先进stack 的先退出
        // 所以应该这样去处理 
        dfs("JFK", flights);
        while(!sta.isEmpty()) {
            path.add(sta.pop());
        }
        return path;
    }

    public void dfs(String depature ,Map<String, PriorityQueue<String>> flights) {
        // get neighbors
        PriorityQueue<String> neighbors =
            flights.getOrDefault(depature, new PriorityQueue<String>());
        while(!neighbors.isEmpty()) {
            // since it will only iterate once due to one path, note the key is to modify the neighbor list while iteration
            // 因为在 dfs 过程中， 也会反复的 push to the stack 的 
            // here, change the neighbors list, poll the nodes out from neighbors list
            dfs(neighbors.poll(), flights);
        }
        // after all the edges are processed put the stack
        sta.push(depature);
    }
}