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 fromJFK. Thus, the itinerary must begin withJFK.

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.

S1: 逆向思维 greedy

构造有向图，只有当一个节点的后继节点全部访问完时才访问该节点

用multiset存储子节点，保证排序。注意multiset删除一个值会将所有等于该值得元素都删除，此处我们只想删除一个元素，所以用iterator来删除

    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        vector<string> result;
        unordered_map<string, multiset<string>> map;
        for (const auto& t : tickets) {
            map[t.first].insert(t.second);
        }
        dfs(map, "JFK", result);
        reverse(result.begin(), result.end());
        return result;
    }

    void dfs(unordered_map<string, multiset<string>>& map, string pre, vector<string>& result) {       
        while (map.find(pre) != map.end() && !map[pre].empty()) {
            string s = *map[pre].begin();
            map[pre].erase(map[pre].begin());
            dfs(map, s, result);
        }        
        result.push_back(pre);
    }

S2: backtracking

  //runtime error, map[pre] erase, insert有问题
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        vector<string> result {"JFK"};
        unordered_map<string, multiset<string>> map;
        for (const auto& t : tickets) {
            map[t.first].insert(t.second);
        }
        dfs(map, "JFK", result, tickets.size() + 1);
        return result;
    }

    bool dfs(unordered_map<string, multiset<string>>& map, string pre, vector<string>& result, int n) {       
        if (map.find(pre) == map.end() || map[pre].empty()) {
            return result.size() == n;
        }
        for(auto i = map[pre].begin(); i != map[pre].end(); ++i) {
            string s = *i;
            map[pre].erase(i);
            result.push_back(s);
            if (dfs(map, s, result, n)) return true;
            map[pre].insert(s);
            result.pop_back();
        }       
        return false;
    }