Reconstruct Itinerary

Reconstruct Itinerary, 这题就是欧拉回路的应用。在DFS之前，用Map维护一个from_city与Queue的关系，把结果存到一个LinkedList里。每次只有当from_city所对应的所有的to_city都走完了，我们才把from_city标记为visited，并且把from_city加到LinkedList的头上。伪代码可以参考Topological Sorting的DFS的代码。

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        Map<String, Queue<String>> map = new HashMap<String, Queue<String>>();
        for (String[] ticket: tickets) {
            if (!map.containsKey(ticket[0])) {
                map.put(ticket[0], new PriorityQueue<String>());
            }
            map.get(ticket[0]).offer(ticket[1]);
        }

        LinkedList<String> result = new LinkedList<String>();
        dfs(result, map, "JFK");

        return result;
    }

    private void dfs(LinkedList<String> result, Map<String, Queue<String>> map, String city) {
        Queue<String> queue = map.get(city);
        while (queue != null && !queue.isEmpty()) {
            String next = queue.poll();
            dfs(result, map, next);
        }

        result.addFirst(city);
    }
}