Reconstruct Itinerary Solutions in C++

// Source : https://leetcode.com/problems/reconstruct-itinerary/
// Author : Hao Chen
// Date   : 2017-01-06



/*
 This problem's description really confuse me.
 
 for examples:
    1) [["JFK", "PEK"], ["JFK", "SHA"], ["SHA", "JFK"]], which has two itineraries: 
       a) JFK -> PEK, 
       b) JFK -> SHA -> JFK -> PEK
       The a) is smaller than b), because PEK < SHA, however the b) is correct answer.
       So, it means we need use all of tickets.
       
    2) [["JFK", "PEK"], ["JFK", "SHA"]], which also has two itineraries:
       a) JFK -> PEK
       b) JFK -> SHA
       for my understanding, the JFK -> SHA is the correct one, 
       however, the correct answer is JFK -> SHA -> PEK.
       I don't understand, why the correct answer is not JFK -> PEK -> SHA
       That really does not make sense to me.
       
 All right, we need assume all of the tickets can be connected in one itinerary.
 Then, it's easy to have a DFS algorithm.
*/


class Solution {
public:
    //DFS
    void travel(string& start, unordered_map<string, multiset<string>>& map, vector<string>& result) {
        while (map[start].size() > 0 ) {
            string next = *(map[start].begin());
            map[start].erase(map[start].begin());
            travel(next, map, result);
        }
        result.insert(result.begin(), start);
    }
    
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string, multiset<string>> map;
        for(auto t : tickets) {
            map[t.first].insert(t.second);
        }
        vector<string> result;
        string start = "JFK";
        travel(start, map, result);
        return result;
    }
};