一文读懂：将问题转化为欧拉路径

对欧拉回路与欧拉路径到这里就结束了。然而，在实际解决问题时，最为困难的往往不是求解欧拉路径本身，而是如何将一个看似不相关的问题转化为欧拉路径。毕竟，300 年前的欧拉也是将现实问题抽象为欧拉回路，才成功解决了哥尼斯堡七桥问题。以下通过两道例题，帮助读者感受欧拉路径的经典应用。

首先考虑这道例题^10。

给你一份航线列表 tickets，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

• 1 <= tickets.length <= 300

这个问题比较容易抽象为图论。我们将机场看成节点，那么机票就是从一座机场指向另一座机场的有向边。由于每张机票都需要恰好使用一次，且必须从 JFK 机场出发，因此本题求的就是从 JFK 出发，且字典序最小的欧拉路径。

由于题目保证了存在欧拉路径，我们可以省去大量判断，直接使用 Hierholzer 算法即可。本题的 C++ 代码如下：

class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { // 构建有向图 unordered_map<string, vector<string>> e; for (auto &ticket : tickets) e[ticket[0]].push_back(ticket[1]); // 把从每个点出发的边，按从大到小的顺序排序 // 从大到小的原因是，dfs 函数每次遍历的是未被删除的【最后一条】边 // 因此为了先遍历编号小的终点，要把它放后面 for (auto &p : e) sort(p.second.begin(), p.second.end(), [](string &a, string &b) { return a > b; }); vector<string> ans; function<void(string)> dfs = [&](string sn) { while (e[sn].size() > 0) { auto fn = e[sn].back(); // 删除有向边 sn -> fn e[sn].pop_back(); // 继续遍历相邻点 dfs(fn); // 将终点 fn 加入结果序列中 ans.push_back(fn); } }; // 根据题目要求，必须从机场 JFK 出发 dfs("JFK"); // 因为 dfs 函数只记录了每次遍历的终点，最开始的起点要额外记一下 ans.push_back("JFK"); // ans 保存的是欧拉路径的倒序，必须 reverse 才是正确答案 reverse(ans.begin(), ans.end()); return ans; } };