Problem description:

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:

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"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 1:
Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:
Input: tickets = [["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.

Solution:

We can first show an example with the graph.

After we have the graph, we can use DFS to solve the problem. We traverse down a path until it stuck, then we go back to previous node and traverse other paths of previous node.

We can use unordered_map to store the paths. multiset can use to help sorting the incoming tickets in smaller lexical order.

The step goes like this:

  1. construct the graph
  2. start visit “JFK”
  3. if “JFK” has paths, then start from the first one, and erase it. To erase it is because we visit the path, if we come back later, we’ll then traverse the second path from “JFK”.
  4. The result is in reverse order. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string, multiset<string>> map;
        vector<string> res;
        
        for(auto n: tickets){
            map[n.first].insert(n.second);
        }
        
        dfs(map, "JFK", res);
        reverse(res.begin(), res.end());
        return res;
    }
    
    void dfs(unordered_map<string, multiset<string>>& map, string s, vector<string>& res){
        while(map[s].size()){
            string tmp= *map[s].begin();
            map[s].erase(map[s].begin());
            dfs(map, tmp, res);
        }
        res.push_back(s);
    }
    
};

reference:
https://goo.gl/xDedxi
http://www.cnblogs.com/grandyang/p/5183210.html