332. Reconstruct Itinerary

This problem is equivalent to find a path that visits each path exactly once, i.e. Eulerian Path. To solve the problem, we start from JFK and visit its neighbors in lexical order. Once we visited a neighbor node, we remove it so that we visit that path only once. Then we move to the neighbor node and do the same thing. Unless we visited all neighbors, we push the current node to the itinerary. Therefore, the itinerary is reversed and we have to do the reversing.
I made two mistakes here as highlighted in red:

1. I was trying to traverse the neighbors by "for (auto it = adj[departure].begin(); it != adj[departure].end(); it++)". The problem is, once you erase a node in the set, the traversal is broken, and you'll probably get a segment fault.

2. I was trying to push the departure before traversing the neighbors. This is an easy mistake to make as it works for some itinerary. However, it won't work for [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]. The reason is at the very beginning, you don't know if current airport is a connection or is the last stop. We only want to push the airport to the itinerary unless it is the last stop. Therefore, we do the push in the end of dfs function.

1:  class Solution {  
2:  public:  
3:    vector<string> findItinerary(vector<pair<string, string>> tickets) {  
4:      unordered_map<string, multiset<string>> adj;  
5:      // build graph  
6:      for (pair<string, string> p : tickets) {  
7:        adj[p.first].insert(p.second);  
8:      }  
9:      vector<string> itinerary;  
10:      helper(adj, itinerary, "JFK");  
11:      reverse(itinerary.begin(), itinerary.end());  
12:      return itinerary;  
13:    }  
14:    void helper(unordered_map<string, multiset<string>> &adj, vector<string> &itinerary, string departure) {  
15:      while (adj[departure].size()) {  
16:        multiset<string>::iterator arrival = adj[departure].begin();  
17:        adj[departure].erase(arrival);  
18:        helper(adj, itinerary, *arrival);  
19:      }  
20:      itinerary.push_back(departure);  
21:    }  
22:  };