【LeetCode】重新安排行程

【问题】给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:
如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。

示例 1:
输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

【思路】将每一对的【起始，终止】的终止与数值连接在一起，初始化为1，表示该终止节点还没有被访问到。接着进行深度搜索，当遍历到该终止节点后，将对应数值减一，则在dfs中不会再进行访问。如果最终的res的size大小为tickets的大小+1，从而结束递归！

class Solution {
public:
    int n = 0;
    vector<string> res, tmp;
    unordered_map<string, map<string, int>> mp;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        n = tickets.size();
        for (auto& v : tickets) ++mp[v[0]][v[1]]; // 标记v[1]还未访问过
        tmp.emplace_back("JFK");
        dfs();
        return res;
    }
    void dfs() {
        if (res.size() == n + 1) return;
        if (tmp.size() == n + 1) {
            res = tmp; return;
        }
        for (auto& p : mp[tmp.back()]) {
            if (!p.second) continue;
            tmp.push_back(p.first);
            --p.second;
            dfs();
            tmp.pop_back();
            ++p.second;
        }
    }
};