/** 
1.题意:  从JFK开始每个边经过一次来遍历所有点, 保证路径的字典序最小, 即字典序最小的有向图欧拉回路
2.建图: 因为可能有重边, 并且保证遍历边的顺序按字典序, 所以可以用优先队列来存边, 也方便每次用完删除
3.搜索:  
3.1 dfs顺序: 
    (1)保证终点最后输出, 因为终点必定出度比入度少一, 所以先将所有出边扩展后删除, 再将点加入结果集, 终点必定最先加入
    (2)因为是按字典序遍历, 所以路径字典序大的一定会先加入
    (3)因为先扩展, 后加点, 所以整个加入顺序是逆序的
3.2 dfs状态: local: node | global: result, graph
4. 结果集逆序即为所求
*/

class Solution {
    static final String start = "JFK";
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, Queue<String>> graph = new HashMap<>();

        for (int i = 0 ; i < tickets.size(); i++){
            String x = tickets.get(i).get(0);
            String y = tickets.get(i).get(1);
            if (graph.get(x) == null) graph.put(x, new PriorityQueue<String>());
            graph.get(x).add(y);
        }

        List<String> result = new ArrayList<>();
        dfs(start, result, graph);
        Collections.reverse(result);
        return result;
    }

    void dfs(String x, List<String> result, Map<String, Queue<String>> graph){
        Queue<String> edges = graph.get(x);
        while (edges != null && !edges.isEmpty())   dfs(edges.poll(), result, graph);
        result.add(x);
    }
}