leetcode-332：重新安排行程

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

class Solution {
public:
    unordered_map<string,map<string,int>> targets;
    bool backtracing(int ticketNum,vector<string>& res){
        if(res.size()==ticketNum+1){
            return true;
        }
        for(pair<const string,int>& target:targets[res[res.size()-1]]){
            if(target.second>0){
                res.push_back(target.first);
                target.second--;
                if(backtracing(ticketNum,res)) return true;
                res.pop_back();
                target.second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> res;
        for(const vector<string> vec:tickets){
            targets[vec[0]][vec[1]]++;
        }
        res.push_back("JFK");
        backtracing(tickets.size(),res);
        return res;
    }
};
java
```java
class Solution {
    List<String> res=new LinkedList<>();
    Map<String,Map<String,Integer>> mp=new HashMap<>();
    boolean dfs(int ticketNum){
        if(res.size()==ticketNum+1) return true;
        String last=res.get(res.size()-1);
        if(mp.containsKey(last)==false) return false; //如果没有该站点始发的车票，那就退出
        for(Map.Entry<String,Integer> entry:mp.get(last).entrySet()){
            String dst=entry.getKey();
            Integer num=entry.getValue();
            if(num>0){
                res.add(dst);
                entry.setValue(num-1);
                if(dfs(ticketNum)) return true;
                res.remove(res.size()-1);
                entry.setValue(num);
            }
        }
        return false;     
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        for(List<String> list:tickets){
            String src=list.get(0);
            String dst=list.get(1);
            Map<String,Integer> tmp;
            if(mp.containsKey(src)==false){
                tmp=new TreeMap<>();
                tmp.put(dst,1);
            }else{
                tmp=mp.get(src);
                tmp.put(dst,tmp.getOrDefault(dst,0)+1);
            }
            mp.put(src,tmp);
        }
        res.add("JFK");
        dfs(tickets.size());
        return res;
    }
}

## <font color=#cc99cc>方法二</font>：Hierholzer 算法
[参考链接](https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/)
![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/2d8cff71a86e4750b2151ddcfb4b55a2.png)
```cpp
class Solution {
public:
    unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;
    vector<string> res;
    void dfs(const string& curr) {
        while (vec.count(curr) && vec[curr].size() > 0) {
            string tmp = vec[curr].top();
            vec[curr].pop();
            dfs(tmp);
        }
        res.emplace_back(curr);
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (vector<string>& it : tickets) {
            vec[it[0]].emplace(it[1]);
        }
        dfs("JFK");
        reverse(res.begin(), res.end());
        return res;
    }
};