题目描述

一个人去旅游，给出旅游途中的所有机票，机票上有起点城市和终点城市[from, to]。请重建出旅游路线。
已知，这个人从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"]. 但是它的字典序并不是最小的。

算法

(有向图欧拉路径) $O(n)$

经典的有限图欧拉路径（一笔画）问题：找到一条路径，遍历所有边，点在路径中可以重复，边不可以重复。

直接从起点开始dfs即可，每次选择一条没有遍历过的边，递归进行遍历。
当把当前节点的所有出边都遍历完时，将该点加入路径序列。
最终记录的路径是真正遍历路径的逆序，所以我们要将记录的路径逆序输出。

题目中要求我们输出字典序最小的路径，直接贪心即可，每次优先选择字典序最小的出边进行遍历。这一步可以用堆或者平衡树来存储每个点的所有出边，在C++中可以用 priority_queue 或者 multiset。

时间复杂度分析：每条边只遍历一次，但需要对每个点的所有出边按字典序排序，所以总时间复杂度是 $O(nlogn)$。

C++ 代码

class Solution {
public:
    unordered_map<string, multiset<string>> g;
    vector<string> ans;

    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        for (auto &ticket : tickets) g[ticket.first].insert(ticket.second);
        dfs("JFK");
        return vector<string>(ans.rbegin(), ans.rend());
    }

    void dfs(string ver)
    {
        while (g[ver].size())
        {
            string next = *g[ver].begin();
            g[ver].erase(g[ver].begin());
            dfs(next);
        }

        ans.push_back(ver);
    }
};