332. Reconstruct Itinerary

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:

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.

-------------------------
Solution #1
很直接的graph traversal，要对edge做visited，而不是node

class Solution {
    
    public List<String> findItinerary(String[][] tickets) {
        Map<String, Node> graph = buildGraph(tickets);
        
        List<String> rt = new ArrayList<>();
        rt.add("JFK");
        dfs(graph.get("JFK"), rt, tickets.length);
        
        return rt;
    }
    
    private boolean dfs(Node node, List<String> rt, int count) {
        if (count == 0) {
            return true;
        }
                
        for (int i = 0; i < node.next.size(); i++) {
            Node n = node.next.get(i);
            rt.add(n.airport);
            
            if (!node.visited[i]) {
                node.visited[i] = true;
                if (dfs(n, rt, count - 1)) return true;
                node.visited[i] = false;
            } 
            
            rt.remove(rt.size() - 1);
        }
        
        return false;
    }
    
    private Map<String, Node> buildGraph(String[][] tickets) {
        Map<String, Node> graph = new HashMap<>();
        
        for (String[] t : tickets) {
            if (!graph.containsKey(t[0])) {
                graph.put(t[0], new Node(t[0]));
            }
            if (!graph.containsKey(t[1])) {
                graph.put(t[1], new Node(t[1]));
            }
            
            graph.get(t[0]).next.add(graph.get(t[1]));
        }
        
        for (Node n : graph.values()) {
            Collections.sort(n.next, (a,b) -> a.airport.compareTo(b.airport));
            n.visited = new boolean[n.next.size()];
        }
        
        return graph;
    }
    
    class Node{
        public String airport;
        public List<Node> next;
        public boolean[] visited;
        public Node(String airport) {
            this.airport = airport;
            next = new ArrayList<>();
        }
    }
}

Solution #2 Eulerian Path Algorithm，题目已经说了路径一定存在
Eulerian Path的特点是一笔画，所有graph里面最多只有1个node有incoming degree - outgoing == 1, 只有一个node outgoing degree - incoming == 1. 所有要么是若干个环状，要么是一个单条路径 ＋ 若干个环状路径。算法就是遇到死路就back tracking继续。（看下面youtube的视频）

ref: https://www.youtube.com/watch?v=8MpoO2zA2l4
Code ref: https://leetcode.com/problems/reconstruct-itinerary/discuss/78768/Short-Ruby-Python-Java-C++

class Solution {
    public List<String> findItinerary(String[][] tickets) {
        Map<String, PriorityQueue<String>> map = new HashMap<>();        
        
        for (String[] t : tickets) {
            if (!map.containsKey(t[0])) {
                map.put(t[0],new PriorityQueue<String>((a,b) -> a.compareTo(b)));
            }
            
            map.get(t[0]).add(t[1]);
        }
        
        List<String> rt = new ArrayList<>();
        dfs(map,rt,"JFK");
        
        Collections.reverse(rt);
        return rt;
    }
    
    private void dfs(Map<String, PriorityQueue<String>> map, List<String> rt, String ap) {
        
        while (map.containsKey(ap) && !map.get(ap).isEmpty()) {
            dfs(map,rt, map.get(ap).poll());
        }
        
        rt.add(ap);
    }
}