# LC 332. Reconstruct Itinerary

### [Problem link](https://leetcode.com/problems/reconstruct-itinerary/)

###### tags: `leedcode` `hard` `python` `c++` `DFS`

You are given a list of airline <code>tickets</code> where <code>tickets[i] = [from_i, to_i]</code> represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from <code>"JFK"</code>, thus, the itinerary must begin with <code>"JFK"</code>. 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 <code>["JFK", "LGA"]</code> has a smaller lexical order than <code>["JFK", "LGB"]</code>.

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg" style="width: 382px; height: 222px;" />

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg" style="width: 222px; height: 230px;" />

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.

**Constraints:**

- <code>1 <= tickets.length <= 300</code>
- <code>tickets[i].length == 2</code>
- <code>from_i.length == 3</code>
- <code>to_i.length == 3</code>
- <code>from_i</code> and <code>to_i</code> consist of uppercase English letters.
- <code>from_i != to_i</code>

## Solution 1 - DFS
#### C++

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> graph;
        
        for (vector<string> ticket: tickets) {
            graph[ticket[0]].push_back(ticket[1]);
        }

        for (auto& [_, dsts]: graph) {
            sort(dsts.rbegin(), dsts.rend());
        }

        vector<string> res;
        vector<string> stack = {"JFK"};

        while (!stack.empty()) {
            string cur = stack.back();
            if (graph.find(cur) != graph.end() && !graph[cur].empty()) {
                stack.push_back(graph[cur].back());
                graph[cur].pop_back();
            } else {
                res.push_back(cur);
                stack.pop_back();
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

>### Complexity
>n = tickets.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(n) |

## Note
[leetcode solution](https://leetcode.com/problems/reconstruct-itinerary/solutions/4041944/95-76-dfs-recursive-iterative/)