# 10 ms short Java Solution using DFS/topological sort, Beats 96 %. Well explained

• ``````     /**
* When you run random custom test cases in editor you will get to know that they require a topological sort to be done on the input.
* For ex feeding [["JFK",NRT],["JFK",KUL]] returns ["JFK","NRT","KUL"] which seems wrong as per the explanation but since input is not a valid itinerary hence the result.
* This problem needs a topological sort in short. Hence do a topological sort after storing nodes in a sorted order.
* Note :-
**Topological sort is used only for DAGs** hence we need to *remove the edges* once it is visited. Thats why the solution uses a priority queue which sorts the nodes as well as helps in removing it in an efficient way.
*/
public List<String> findItinerary(String[][] tickets) {
HashMap<String,PriorityQueue<String>> graph = new HashMap<>();
for(String[] edge : tickets){
if(!graph.containsKey(edge[0]))
graph.put(edge[0],new PriorityQueue<>());
graph.get(edge[0]).offer(edge[1]);
}
DFS("JFK",graph,result); // we need to do DFS/topological sort only from "JFK"
return result;
}
/*DFS doing topological sort*/
private void DFS(String node,HashMap<String,PriorityQueue<String>> graph,LinkedList<String> result ){
PriorityQueue<String> nodes = graph.get(node);
while(nodes!= null && !nodes.isEmpty())
DFS(nodes.poll(),graph,result);