Reconstruct Itinerary -- LeetCode

[Question]

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:
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.

[Analysis]
The assumption -- "all tickets form at least one valid itinerary" is strong. That means there is a path which will consume all given tickets. As the itinerary can compose a directed graph (DiGraph), the problem is to find a one path which go through all edges (note: some vertexes can be visited many times).

Using DFS to visit all edges will solve the problem. When all edges are visited, the number of vertices in the stack should be equal to the number of tickets plus one (then the DFS recursion can be finished at this moment).

[Solution]
class Solution {
public:
    bool dfs (unordered_map<string, map<string, int>> &maps, vector<string>& rslt, int length) {
        if (rslt.size() == length) return true;
        bool ret;
        for(auto& dst: maps[rslt.back()] ) {
            if (dst.second!=0) {
                rslt.push_back(dst.first);
                dst.second--;
                ret = dfs(maps, rslt, length);
                if (ret) return true;
                dst.second++;
                rslt.pop_back();
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        if (tickets.empty() ) return vector<string>();
       
        unordered_map<string, map<string, int> > maps;
        for (const auto& t: tickets) {
            maps[t.first][t.second]++;
        }
       
        vector<string> rslt;
        rslt.push_back("JFK");
        dfs (maps, rslt, tickets.size()+1);
       
        return rslt;
  }
};