1
class Solution {
2
 public:
3
  vector<string> findItinerary(vector<vector<string>> &tickets) {
4
    unordered_map<string, multiset<string>> myMap;
5
    stack<string> myStack;
6
    vector<string> ans;
7
    for (int i = 0; i < tickets.size(); ++i) {
8
      myMap[tickets[i][0]].insert(tickets[i][1]);
9
    }
10
    myStack.push({"JFK"});
11
    while (!myStack.empty()) {
12
      string top = myStack.top();
13
      if (!myMap[top].empty()) {
14
        myStack.push(*myMap[top].begin());
15
        myMap[top].erase(myMap[top].begin());
16
      } else {
17
        ans.insert(ans.begin(), top);
18
        myStack.pop();
19
      }
20
    }
21
    return ans;
22
  }
23
};
24
// Time : O(E)
25
// Space : O(V + E)