## # 332. Reconstruct Itinerary

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:
``````Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
``````

Example 2:

``````Input: [["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.
``````

Approach 1: DFS.

Approach 1:

### # Code (C++)

Approach 1:

``````class Solution {
private:
vector<string> res;
bool findRes;
int total;
int cmp(string a, string b) {
for (int i = 0; i < a.size(); ++i)
{
if (a[i] > b[i])
return 1;
else if (a[i] < b[i])
return -1;
}
return 0;
}
void doFindItinerary(string start, vector<string>& path) {
path.push_back(start);
total--;
if (total == 0)
{
res = path;
findRes = true;
}
else
{
{
string next = *it;
doFindItinerary(next, path);
if (findRes)
break;
}
}
path.pop_back();
total++;
}
void doFindItinerary(string start) {
{
doFindItinerary(next);
}
res.push_back(start); // Need to be here instead of before while().
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
findRes = false;
total = tickets.size() + 1;
for (int i = 0; i < tickets.size(); ++i)
{
string start = tickets[i];
string end = tickets[i];
for (; it != links[start].end(); ++it)
{
if (cmp(*it, end) > 0)
break;
}