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:

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:

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

Example 2:

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.

// Recursive DFS
void dfs(unordered_map<string, multiset<string> >& graph, const string& s, vector<string>& res) {
    while (!graph[s].empty()) {
        string t = *(graph[s].begin());
        graph[s].erase(graph[s].begin());
        dfs(graph, t, res);
    }
    res.emplace_back(s);
}
vector<string> findItinerary(vector<vector<string>>& tickets) { // time: O(V + E); space: O(V + E)
    vector<string> res;
    unordered_map<string, multiset<string> > graph; // adjacency list
    for (auto& t : tickets) {
        graph[t[0]].insert(t[1]);
    }
    dfs(graph, "JFK", res);
    return vector<string>(res.rbegin(), res.rend());
}

// Iterative DFS
vector<string> findItinerary(vector<vector<string>>& tickets) { // time: O(V + E); space: O(V + E)
    vector<string> res;
    unordered_map<string, multiset<string> > graph; // adjacency list
    for (auto& t : tickets) {
        graph[t[0]].insert(t[1]);
    }
    stack<string> st({"JFK"});
    while (!st.empty()) {
        string t = st.top();
        if (graph[t].empty()) {
            res.emplace_back(t);
            st.pop();
        } else {
            st.push(*graph[t].begin());
            graph[t].erase(graph[t].begin());
        }
    }
    return vector<string>(res.rbegin(), res.rend());
}