332. Reconstruct Itinerary |

题目

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:

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”].
All airports are represented by three capital letters (IATA code).

You may assume all tickets form at least one valid itinerary.

Example 1:

1 2	Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

1
2
3

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].But it is larger in lexical order.

解题思路

本题是关于图的边进行遍历，每张机票都是图的一条有向边，需要找出经过每条边的路径，并且必定有解本题，则对于某个节点（非起点）其只于一个节点相邻且只存在一条边，则这个节点必定是最后访问的，否则不可能遍历完所有边，并且这种点最多一个（不包含起点）。

解法 1 — `DFS + 递归`

解决步骤
- 将图建立起来，建立邻接表，使用map<string, multiset<string> 来存储邻接表。使用multiset可以自动排序。（set的默认排序由小到大，multiset默认排序是由大到小）
- 从节点JKF开始DFS遍历，只要当前的映射集合multiset里面还有节点，则取出这个节点，递归遍历这个节点，同时需要将这个节点从multiset中删除掉，当映射集合multiset为空的时候，则将节点加入到结果中
- 因为当前存储结果是回溯得到的，需要将结果的存储顺序反转输出

实现代码

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        vector<string> v;
        map<string, multiset<string> > myMap;
        for(auto it : tickets)
            myMap[it.first].insert(it.second);

        dfs("JFK", v, myMap);
        reverse(v.begin(), v.end());
        return v;
    }

    void dfs(string start, vector<string>& v, map<string, multiset<string> > &myMap) {
        while(myMap[start].size() > 0) {
            string next = *myMap[start].begin();
            myMap[start].erase(myMap[start].begin());
            dfs(next, v, myMap);
        }
        v.push_back(start);
    }
};

解法 2 — `DFS + 迭代`

思路与解法一相同，利用数据结构stack进行迭代。

实现代码

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        vector<string> v;
        map<string, multiset<string> > myMap;
        for(auto it : tickets)
            myMap[it.first].insert(it.second);

        stack<string> myStack;
        myStack.push("JFK");
        while(!myStack.empty()) {
            string node = myStack.top();
            
            if(!myMap[node].size()) {
                myStack.pop();
                v.push_back(node);
            } 
            else {
                myStack.push(*myMap[node].begin());
                myMap[node].erase(myMap[node].begin());
            }
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

题目

解题思路

解法 1 — DFS + 递归

解法 2 — DFS + 迭代

解法 1 — `DFS + 递归`

解法 2 — `DFS + 迭代`