## Algorithm

Problem Name: 332. Reconstruct Itinerary

You are given a list of airline `tickets` where `tickets[i] = [fromi, toi]` 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 `"JFK"`, thus, the itinerary must begin with `"JFK"`. 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"]`.

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

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

Constraints:

• `1 <= tickets.length <= 300`
• `tickets[i].length == 2`
• `fromi.length == 3`
• `toi.length == 3`
• `fromi` and `toi` consist of uppercase English letters.
• `fromi != toi`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int cmp(const void *a, const void *b) {
const char **s1 = *(const char ***)a, **s2 = *(const char ***)b;
int c = strcmp(s1[0], s2[0]);
if (c) return c;
return strcmp(s1[1], s2[1]);
}
int dfs(int *v, char ***tickets, int n, char **p, int last, int d) {
int i;

if (d == n) {
p[n] = tickets[last][1];
return 1;
}

for (i = 0; i  <  n; i ++) {
if (!v[i] && !strcmp(tickets[last][1], tickets[i][0])) {
v[i] = 1;
p[d] = tickets[i][0];
if (dfs(v, tickets, n, p, i, d + 1)) return 1;
v[i] = 0;
}
}

return 0;
}
char** findItinerary(char*** tickets, int ticketsRowSize, int ticketsColSize, int* returnSize) {
int *v, i, done;
char **p;

qsort(tickets, ticketsRowSize, sizeof(char **), cmp);

p = malloc((ticketsRowSize + 1) * sizeof(char *));
v = calloc(ticketsRowSize, sizeof(int));
//assert(p && v);

done = 0;
for (i = 0; !done && i  <  ticketsRowSize; i ++) {
if (!strcmp(tickets[i][0], "JFK")) {
v[i] = 1;
p[0] = tickets[i][0];
done = dfs(v, tickets, ticketsRowSize, p, i, 1);
v[i] = 0;
}
}

*returnSize = ticketsRowSize + 1;
free(v);

return p;
}
``````
Copy The Code &

Input

cmd
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output

cmd
["JFK","MUC","LHR","SFO","SJC"]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<string> findItinerary(vector<pair, greaterm;
vector < string>res;
for(auto x: tickets) m[x.first].push(x.second);
DFS("JFK", res, m);
reverse(res.begin(), res.end());
return res;
}

void DFS(string cur, vector < string>& res, unordered_map, greater& m){
while(!m[cur].empty()){
string s = m[cur].top();
m[cur].pop();
DFS(s, res, m);
}
res.push_back(cur);
}
};
``````
Copy The Code &

Input

cmd
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output

cmd
["JFK","MUC","LHR","SFO","SJC"]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List findItinerary(List();
for (List ticket : tickets) {
String from = ticket.get(0);
String to = ticket.get(1);
map.computeIfAbsent(from, k -> new PriorityQueue < >()).add(to);
}
Stack stack = new Stack<>();
stack.push("JFK");
while (!stack.isEmpty()) {
String destination = stack.peek();
if (!map.getOrDefault(destination, new PriorityQueue < >()).isEmpty()) {
stack.push(map.get(destination).remove());
} else {
}
}
return result;
}
}
``````
Copy The Code &

Input

cmd
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output

cmd
["JFK","ATL","JFK","SFO","ATL","SFO"]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findItinerary(self, tickets):
graph, stack, reached = collections.defaultdict(list), ["JFK"], []
for a, b in tickets: heapq.heappush(graph[a], b)
while stack:
if graph[stack[-1]]: stack.append(heapq.heappop(graph[stack[-1]]))
else: reached.append(stack.pop())
return reached[::-1]
``````
Copy The Code &

Input

cmd
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output

cmd
["JFK","ATL","JFK","SFO","ATL","SFO"]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0332_ReconstructItinerary
{
public IList < string> FindItinerary(IList();
foreach (var ticket in tickets)
{
if (!map.ContainsKey(ticket[0]))
map[ticket[0]].Insert(ticket[1]);
}

var result = new List < string>();
Visit("JFK", map, result);
return result;
}

private void Visit(string airport, IDictionary < string, MinPriorityQueue> map, IList route)
{
while (map.ContainsKey(airport) && map[airport].Size() > 0)
{
var target = map[airport].DeleteMin();
Visit(target, map, route);
}
route.Insert(0, airport);
}

public class MinPriorityQueue : PriorityQueue
{
public MinPriorityQueue() : base() { }

public MinPriorityQueue(int initCapacity) : base(initCapacity) { }

protected override void Sink(int k)
{
while (2 * k  < = N)
{
int j = 2 * k;
if (j < N && pq[j].CompareTo(pq[j + 1]) > 0) j++;
if (pq[k].CompareTo(pq[j])  < = 0) break;
Swap(k, j);
k = j;
}
}

protected override void Swim(int k)
{
while (k > 1 && pq[k / 2].CompareTo(pq[k]) > 0)
{
Swap(k / 2, k);
k = k / 2;
}
}

public string Min() => First();

public string DeleteMin() => Delete();
}

public abstract class PriorityQueue
{
protected int N;
protected string[] pq;

public PriorityQueue() : this(1) { }

public PriorityQueue(int initCapacity)
{
this.N = 0;
pq = new string[initCapacity + 1];
}

public bool IsEmpty() => N == 0;

public int Size() => N;

public string First()
{
if (IsEmpty()) { throw new ArgumentOutOfRangeException(); }
return pq[1];
}

public void Insert(string x)
{
if (N >= pq.Length - 1)
Resize(pq.Length * 2);

pq[++N] = x;
Swim(N);
}

protected abstract void Swim(int k);

public string Delete()
{
var result = pq[1];
Swap(1, N--);
Sink(1);
pq[N + 1] = string.Empty;
if (N > 0 && N == (pq.Length - 1) / 4)
Resize(pq.Length / 2);

return result;
}

protected abstract void Sink(int k);

private void Resize(int newCapacity)
{
var temp = new string[newCapacity + 1];
for (int i = 1; i  < = N; i++)
temp[i] = pq[i];

pq = temp;
}

protected void Swap(int index1, int index2)
{
var temp = pq[index1];
pq[index1] = pq[index2];
pq[index2] = temp;
}
}
}
}
``````
Copy The Code &

Input

cmd
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output

cmd
["JFK","MUC","LHR","SFO","SJC"]