332. Reconstruct Itinerary（重建行程）

• Reconstruct Itinerary重建行程
  • 题目链接
  • 题目描述
  • 题目分析
    • 方法深搜
  • 参考代码

题目链接

https://leetcode.com/problems/reconstruct-itinerary/description/

题目描述

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:
1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目分析

这道题的解法看起来很明了，按照题目要求显然是DFS。不过，题目要求要遍历所有节点，一次深搜不一定会得到能遍历所有节点的路径。因此，需要加入回溯。不过，往往最容易想到的方法都不是很快的。深搜加回溯非常耗时，最坏的情况下需要尝试过所有可能的深搜路径才能找到解，时间复杂度为O(n²)。

换一个角度来看这个问题，事实上题目中所给的图都很特殊。因为一条路径遍历所有的节点，那么最后一个节点一定出度为0。套上这个题目的情景就更好理解了，最后一个节点就是终点，到达终点后就不会再前往任何地方了，所以出度必然是0。需要注意的是：这里说的出度为0并不是说这个节点只作为目的地出现而不作为出发地出现，而是说当访问到这个节点时它没有未访问过的边。

上图是一个简单的例子，当第二次访问到JFK时，它已经没有边可以访问了。

往回考虑倒数第二个节点，它只能有一条未访问过的边（即指向终点的边）。可以用反证法证明：假设它有多条未访问过的边，那么当到达终点时仍然有未访问过的节点，所以此终点并非终点，这就跟假设矛盾了。所以当访问过终点后，倒数第二个节点也无边可访问（出度为0）。这样一来，我们只用DFS就可以找到解了，时间复杂度为O(n)。

方法：深搜

算法描述

1. 生成图，在生成过程中，需注意当前节点所能到达的节点应该按字典序排序
2. 从题目要求的JFK开始做DFS，每次DFS按照字典序从小到大选择下一个访问的节点，当访问到出度为0的节点时把它压栈

参考代码

class Solution {
public:
    struct cmp
    {
        bool operator()(const string& a, const string& b) {
            return a > b;
        }
    };

    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        map<string, int> m;
        vector<priority_queue<string, vector<string>, cmp > > queues;
        for (auto p : tickets) {
            if (m.find(p.first) == m.end()) {
                priority_queue<string, vector<string>, cmp> newQueue;
                newQueue.push(p.second);
                queues.push_back(newQueue);
                m.insert(make_pair(p.first, queues.size() - 1));
            }
            else {
                queues[m[p.first]].push(p.second);
            }
        }

        vector<string> ans;
        stack<string> visitedPlaces;
        visitedPlaces.push("JFK");

        while (!visitedPlaces.empty()) {
            string current = visitedPlaces.top();
            if (m.find(current) == m.end() || queues[m[current]].size() == 0) {
                ans.push_back(current);
                visitedPlaces.pop();
            }
            else {
                visitedPlaces.push(queues[m[current]].top());
                queues[m[current]].pop();
            }
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};