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.

&nbsp;
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.


&nbsp;
Constraints:


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


class Solution:        
    def findTicketsAdjList(self, tickets):
        ticket = {}
        for src,dest in tickets:
            if src in ticket:
                ticket[src].append(dest)
            else:
                ticket[src] = [dest]

        for src,dest in ticket.items():
            if len(dest)>1:
                ticket[src] = sorted(ticket[src], reverse=True)
                
        return ticket
    
    def reconstructItinerary(self, source, tickets, itinerary):
        if source in tickets:
            while tickets[source]:        
                destination = tickets[source].pop()
                self.reconstructItinerary(destination, tickets, itinerary)
        itinerary.append(source)
        return itinerary
                        
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        if len(tickets)==1:
            if "JFK" not in tickets[0]:
                return []
            
        ticketsAdj = self.findTicketsAdjList(tickets)
        if "JFK" not in ticketsAdj:
            return []
        itinerary = []
        itinerary = self.reconstructItinerary("JFK", ticketsAdj, itinerary)
        
        return itinerary[::-1]
        
class Solution {
    LinkedList<String> res = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        HashMap<String,PriorityQueue<String>> map= new HashMap<>();
        for(int i=0;i<tickets.size();i++){
            String a=tickets.get(i).get(0);
            String b=tickets.get(i).get(1);
            if(!map.containsKey(a)){
                PriorityQueue<String> temp = new PriorityQueue();
                map.put(a,temp);
            }
            map.get(a).add(b);
        }

        dfs("JFK",map);
        return res;

    }
    private void dfs(String departure,HashMap<String,PriorityQueue<String>> map){
        PriorityQueue<String> arrivals= map.get(departure);
        while(arrivals!=null &&!arrivals.isEmpty()){
            dfs(arrivals.poll(),map);
        }
        res.addFirst(departure);
    }
}
class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, multiset<string>> myMap;
        stack<string> myStack;
        vector<string> ans;
        for (int i=0; i<tickets.size(); ++i) {
            myMap[tickets[i][0]].insert(tickets[i][1]);
        }
        myStack.push({"JFK"});
        while (!myStack.empty()) {
            string top = myStack.top();
            if (!myMap[top].empty()) {
                myStack.push(*myMap[top].begin());
                myMap[top].erase(myMap[top].begin());
            } else {
                ans.insert(ans.begin(), top);
                myStack.pop();
            }
        }
        return ans;
    }
};
// Time : O(E)
// Space : O(V + E)
function dfs(edges,s=`JFK`,ans=[`JFK`]){  //run dfs, starting node being `JFK`
    if(!edges[s] || edges[s].length==0){  //if currenctly reached node has its adjacent list empty
        let isAllTravelled=1;
        Object.values(edges).forEach(ele=> {if(ele.length>0) isAllTravelled=0}) // check if every edge has been travelled i.e all adjacentLists should be empty
         if(!isAllTravelled) return false;   //returns false when there are more edges to travel , but from current node we cannot move anywhere else 
        else return  ans; // return true if from current node we cannot move anywhere else and all the edges have been travelled as well
    }
    
    let myAL= edges[s].sort();  // sort the Adjacency List  of current node lexicographically
    for(let i=0;i<myAL.length;i++){ // start by taking the lexicographically smallest node and run dfs
        ans.push(myAL[i]);  // add current node into answer array
        edges[s]= [...edges[s].slice(0,edges[s].indexOf(myAL[i])),...edges[s].slice(edges[s].indexOf(myAL[i])+1)]; // remove the currently edges travelled from adjacency List 
        let xx= dfs(edges,myAL[i],ans); //here runs the dfs
        if(!xx){ // if dfs result of current node could not travel all edges from current node
            ans.pop(); // pop out current accounted node from answer
            edges[s].push(myAL[i]);  //put back the edge into adjacency list assmuing we should not visit this edge at this point as it doesnt leads to answer from here currenlt
        }
        else return xx ; // if dfs result of current node could travel all edges from current node return the answer array
    } 
}
var findItinerary = function(tickets) {
    let edges={}; //our adjacency list
    tickets.forEach(ticket=>{
       if(!edges[ticket[0]]){
            edges[ticket[0]]=[];
        }
        edges[ticket[0]].push(ticket[1]);
    })
   
    let ans= dfs(edges); // run dfs 
    return ans;
};
Reconstruct Itinerary