【问题】给定一个机票的字符串二维数组 [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; } } };
原文：https://www.cnblogs.com/zhudingtop/p/11707249.html