// @Title: 重新安排行程 (Reconstruct Itinerary)
// @Author: qisiii
// @Date: 2024-09-21 16:57:42
// @Runtime: 7 ms
// @Memory: 44.4 MB
// @comment: 
// @flag: 
class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> map = new HashMap<>();
        // 构造航班信息-始发站：终点站
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            List<String> targets = map.getOrDefault(from, new ArrayList<>());
            targets.add(ticket.get(1));
            map.put(from, targets);
        }
        // 字典序
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            entry.getValue().sort(String::compareTo);
        }
        List<String> result = new ArrayList<>();
        dfs(map, result, "JFK");
        Collections.reverse(result);
        return result;
    }

    private void dfs(Map<String, List<String>> map, List<String> result, String from) {
        List<String> targets = map.get(from);
        while(targets!=null&&targets.size()>0){
            String target = targets.remove(0);
            dfs(map, result, target);
        }
        result.add(from);
    }

    private boolean isFinish(Map<String, List<String>> map) {
        for (List<String> value : map.values()) {
            if (value.size() != 0) {
                return false;
            }
        }
        return true;
    }
}