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:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution:

Classic DFS,

Create a map to maintain the mapping for departure city and all arrival cities, sort all arrived cities because we need the result to have the smallest lexical order.

DFS from JFK, set the destiny city as "#" to mark it as visited, return result when it covers all the egdes, because we sorted all the destiny cities before hand, the first valid result are guaranteed to be the smallest one. 

 public List<String> findItinerary(String[][] tickets) {  
     HashMap<String,List<String>> map=new HashMap<String,List<String>>();  
     for(int i=0;i<tickets.length;i++){  
       if(!map.containsKey(tickets[i][0])) map.put(tickets[i][0],new ArrayList<String>());  
       map.get(tickets[i][0]).add(tickets[i][1]);  
     }  
     for(List<String> item: map.values()){  
       Collections.sort(item);  
     }  
     List<String> res=new ArrayList<String>();  
     DFSHelper(map,"JFK",tickets.length+1,res);  
     return res;      
   }  
   public boolean DFSHelper(HashMap<String,List<String>> map, String cur,int n, List<String> res){  
     res.add(cur);  
     if(res.size()==n) return true;  
     if(!map.containsKey(cur)){  
       res.remove(res.size()-1);  
       return false;  
     }  
     List<String> destinations=map.get(cur);  
     for(int i=0;i<destinations.size();i++){  
       if(!destinations.get(i).equals("#")){  
         String next=destinations.get(i);  
         destinations.set(i,"#");  
         if(DFSHelper(map,next,n,res)) return true;  
         destinations.set(i,next);  
       }  
     }  
     res.remove(res.size()-1);  
    return false;  
   }  
 }  

A better and more concise solution by doing following optimization:
We can use a priorityQueue to maintain the destiny city, which could remove the individual sorting for each map.value(). In terms of time complexity, they are the same.
We can add city from tail to head because any city that doesn't have any outage degree should be added to the tail of current all unfinished cities.

Hierholzer's algorithm to solve Eulerian path (to visit all the path exactly once)

https://en.wikipedia.org/wiki/Eulerian_path
Keep going forward until you get stuck, add the stuck point to the list then backtrack and repeat till all nodes have degree of 0.
   

  public List<String> findItinerary(String[][] tickets) {  
     HashMap<String,PriorityQueue<String>> map=new HashMap<String,PriorityQueue<String>>();  
     int n=tickets.length;  
     for(int i=0;i<n;i++){  
       if(!map.containsKey(tickets[i][0])) map.put(tickets[i][0],new PriorityQueue<String>());  
       map.get(tickets[i][0]).offer(tickets[i][1]);  
     }  
     List<String> res=new LinkedList<String>();  
     dfsHelper(res,map,"JFK");  
     return res;  
   }  
   public void dfsHelper(List<String> res, HashMap<String,PriorityQueue<String>> map, String airport){  
     while(map.containsKey(airport)&& map.get(airport).size()!=0){  
       dfsHelper(res,map,map.get(airport).poll());  
     }  
     res.add(0,airport);  
   }