重新安排行程

题目

332. 重新安排行程

---

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi 和 toi 由大写英文字母组成
• fromi != toi

题解

方法一：

思路

由于一定存在合理行程，所以航线列表构成一个欧拉图或半欧拉图。

• 若为欧拉图，所有点的入度=出度，起点JFK出发一定会回到JFK。
• 若为半欧拉图，起点JFK的出度-入度=1，还存在一个入度-出度=1的点作为终点机场。

使用Hierholzer算法可以求出欧拉路径/回路。

对于欧拉图，我们可以从任意点出发进行dfs，我们每走过一条边就删除掉经过的边，对于没有边可走的点加入到栈中，最后出栈序列就是经过欧拉回路的节点序列。

对于半欧拉图，我们必须从出度=入度+1的点出发，在入度=出度+1的点结束。这样可以得到欧拉路径。

对于本题，我们还需要考虑字典序最小的序列。可以用一个优先队列保存每个点的边，优先走指向字典序较小的点的边，并且这对于删除边也比较方便。当某个点的优先队列为空时，则加入栈并回溯。

代码

class Solution {
public:
    unordered_map<string, priority_queue<string, vector<string>, greater<>>> mp;
    vector<string> ans;
    void dfs(string a) {
        while (mp.count(a) && mp[a].size()) {
            string u = mp[a].top(); mp[a].pop();
            dfs(u);
        }
        ans.push_back(a);
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& i:tickets) {
            mp[i[0]].push(i[1]);
        }
        dfs("JFK");
        reverse(ans.begin(), ans.end());
        return ans;
    }
};