# LeetCode Reconstruct Itinerary

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

```class Solution {
private:
bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) {
if (lines == 0) return true;
int n = hash2.size();
for (int i = 0; i < n; ++i) { // 字典序从小到大深搜
if (graph[start][i] > 0) {
--graph[start][i];
ans += hash2[i];
if (dfs(ans, hash2, graph, i, lines - 1))return true;
++graph[start][i];
ans = ans.substr(0, ans.size() - 3);
}
}
return false;
}
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
map<string, int> hash1;
vector<string> hash2;
int cnt = 0, n = tickets.size();
for (int i = 0; i < tickets.size(); ++i) { // 记录
hash1[tickets[i].first] = 0;
hash1[tickets[i].second] = 0;
}
for (auto it = hash1.begin(); it != hash1.end(); ++it) {
it->second = cnt++; // 字典序从小到大编号
hash2.push_back(it->first);
}

vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图
for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]];

int start = hash1["JFK"];
string ans = "JFK";
dfs(ans, hash2, graph, start, n); // 深搜

vector<string> Itinerary;
for (int i = 0; i <= ans.size() - 3; i += 3)Itinerary.push_back(ans.substr(i, 3));

return Itinerary;
}
};
```