The idea of this algorithm, which was originally found in fangyang's thread https://leetcode.com/discuss/84706/sharesolutionjavagreedystack15mswithexplanation, consists of two steps:

Step 1: Store the flight in a hash map. (say
m
in the code below. This map enables us to find all possible destinations from a place in amortized constant time.) 
Step 2: Use a greedy and traceback approach to find the optimal itinerary. Specifically, we use greedy method to find a lexicographicallysmallest path until we can not move any further (the path can be stored in a vector, say
march
in the code below). Each time we reach such an exhaustive state, we find a place which is exactly the end of the itinerary. (The reason is, the pathmarch
is an optimal itinerary expect that some loops are omitted. The optimal itinerary can be obtained by inserting some loops into this path, which does not change the last vertex of the path.) Therefore, we can record the last vertex in another place (sayresults
in the code below). So and so forth, the vectorresults
stores the optimal itinerary reversely, since we always place the optimal last vertex at the end of this vector. Reversing the vertexresults
leads to the correct answer.
Example:
This example is originally shown in StefanPochmann's thread https://leetcode.com/discuss/84659/shortrubypythonjavac
[ Source of this picture: http://www.stefanpochmann.info/misc/reconstructitinerary.png ]
In Step 2, we first march greedily, and get the vector march
as:
march: JFK > A > C > D > A (the red path)
However, the optimal itinerary, is
JFK > A > C > D( > B > C > JFK > D) > A
where the loop (D > B > C > JFK > D) shall be inserted in the vector march
. However, we have already found the last vertex A, Therefore, we can record this result. So march
and results
become
march: JFK > A > C > D
results: A
Then we march greedily again, results in
march: JFK > A > C > D > B > C > JFK > D
results: A
Now all edges are used. Before the final reversion, march
and results
become
march: (empty)
results: A < D < JFK < C < B < D < C < A < JFK
Overall Complexities:
Let N be the number of tickets. Let D be the largest outgoing degree of a vertex.
 Time: O(N log D)
Step 1: O(N log D)
Step 2: O(N). Each vertex needs to be put intomarch
once and be moved frommarch
toresults
. At the very end,results
is reversed.  Space: O(N)
The mapm
needs to store all vertices.
Code (40 ms):
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
// Step 1: Store directed edges in a hash map
unordered_map<string, multiset<string>> m;
for (const pair<string, string> & ticket : tickets) {
m[ticket.first].insert(ticket.second);
}
// Step 2: March greedily and traceback
vector<string> march = { "JFK" }; // the storage for greedy searching
vector<string> results; // store the final results reversely
while (march.empty() == false) {
string & from = march.back();
if ((m.find(from) != m.end()) && (m[from].empty() == false)) { // march further
multiset<string> & to = m[from];
march.push_back(*(to.begin()));
to.erase(to.begin());
} else { // can not march further, trace back
results.push_back(march.back()); // archive the last place
march.pop_back();
}
}
reverse(results.begin(), results.end()); // reverse the entries back
return results;
}
};