#include <stdlib.h>
#include <string.h>
#define CODES (26 * 26 * 26) // airport codes are 3 uppercase letters
static int code(const char *s) {
return ((s[0] - 'A') * 26 + (s[1] - 'A')) * 26 + (s[2] - 'A');
}
static int cmpDesc(const void *a, const void *b) {
return strcmp(*(char *const *)b, *(char *const *)a);
}
// C has no heap of strings: sort each destination list descending
// and pop from the back, which yields the smallest first
static char ***adj;
static int *adjLen;
static char **result;
static int resultLen;
static void dfs(char *cur) {
int c = code(cur);
while (adjLen[c] > 0) {
char *next = adj[c][--adjLen[c]]; // use this ticket
dfs(next);
}
result[resultLen++] = cur; // post-order: no tickets left here
}
char **findItinerary(char ***tickets, int ticketsSize, int *ticketsColSize,
int *returnSize) {
(void)ticketsColSize; // always 2
adj = calloc(CODES, sizeof(char **));
adjLen = calloc(CODES, sizeof(int));
int *adjCap = calloc(CODES, sizeof(int));
for (int i = 0; i < ticketsSize; i++) {
int c = code(tickets[i][0]);
if (adjLen[c] == adjCap[c]) {
adjCap[c] = adjCap[c] ? 2 * adjCap[c] : 2;
adj[c] = realloc(adj[c], adjCap[c] * sizeof(char *));
}
adj[c][adjLen[c]++] = tickets[i][1];
}
for (int c = 0; c < CODES; c++)
if (adjLen[c] > 1)
qsort(adj[c], adjLen[c], sizeof(char *), cmpDesc);
result = malloc((ticketsSize + 1) * sizeof(char *));
resultLen = 0;
dfs("JFK");
for (int i = 0; i < resultLen / 2; i++) {
char *t = result[i];
result[i] = result[resultLen - 1 - i];
result[resultLen - 1 - i] = t;
}
for (int c = 0; c < CODES; c++)
free(adj[c]);
free(adj);
free(adjLen);
free(adjCap);
*returnSize = resultLen;
return result; // points into tickets, plus the literal "JFK"
}
#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
unordered_map<string, priority_queue<string, vector<string>, greater<>>> adj;
vector<string> result;
void dfs(const string &cur) {
auto &dests = adj[cur];
while (!dests.empty()) {
string next = dests.top();
dests.pop(); // use this ticket
dfs(next);
}
result.push_back(cur); // post-order: no tickets left here
}
public:
vector<string> findItinerary(vector<vector<string>> &tickets) {
for (auto &t : tickets)
adj[t[0]].push(t[1]);
dfs("JFK");
reverse(result.begin(), result.end());
return result;
}
};
package graphs
import "sort"
func findItinerary(tickets [][]string) []string {
// destinations sorted descending, so popping from the back yields the smallest
adj := map[string][]string{}
for _, t := range tickets {
adj[t[0]] = append(adj[t[0]], t[1])
}
for _, dests := range adj {
sort.Sort(sort.Reverse(sort.StringSlice(dests)))
}
result := []string{}
var dfs func(cur string)
dfs = func(cur string) {
for len(adj[cur]) > 0 {
dests := adj[cur]
next := dests[len(dests)-1]
adj[cur] = dests[:len(dests)-1] // use this ticket
dfs(next)
}
result = append(result, cur) // post-order: no tickets left here
}
dfs("JFK")
for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
result[i], result[j] = result[j], result[i]
}
return result
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
class Solution {
private final Map<String, PriorityQueue<String>> adj = new HashMap<>();
private final List<String> result = new ArrayList<>();
private void dfs(String cur) {
PriorityQueue<String> dests = adj.get(cur);
while (dests != null && !dests.isEmpty())
dfs(dests.poll()); // use this ticket
result.add(cur); // post-order: no tickets left here
}
public List<String> findItinerary(List<List<String>> tickets) {
for (List<String> t : tickets)
adj.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
dfs("JFK");
Collections.reverse(result);
return result;
}
}
/**
* @param {string[][]} tickets
* @return {string[]}
*/
var findItinerary = function (tickets) {
// destinations sorted descending, so pop() yields the smallest
const adj = new Map();
for (const [from, to] of tickets) {
if (!adj.has(from)) adj.set(from, []);
adj.get(from).push(to);
}
for (const dests of adj.values()) dests.sort().reverse();
const result = [];
const dfs = (cur) => {
const dests = adj.get(cur) ?? [];
while (dests.length) dfs(dests.pop()); // use this ticket
result.push(cur); // post-order: no tickets left here
};
dfs("JFK");
return result.reverse();
};
import heapq
from collections import defaultdict
from typing import List
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = defaultdict(list) # airport -> min-heap of destinations
for frm, to in tickets:
heapq.heappush(adj[frm], to)
result = []
def dfs(cur: str) -> None:
dests = adj[cur]
while dests:
dfs(heapq.heappop(dests)) # use this ticket
result.append(cur) # post-order: no tickets left here
dfs("JFK")
return result[::-1]
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
impl Solution {
pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
// airport -> min-heap of destinations
let mut adj: HashMap<String, BinaryHeap<Reverse<String>>> = HashMap::new();
for t in tickets {
adj.entry(t[0].clone()).or_default().push(Reverse(t[1].clone()));
}
let mut result = Vec::new();
Self::dfs("JFK".to_string(), &mut adj, &mut result);
result.reverse();
result
}
fn dfs(cur: String, adj: &mut HashMap<String, BinaryHeap<Reverse<String>>>, result: &mut Vec<String>) {
while let Some(Reverse(next)) = adj.get_mut(&cur).and_then(|dests| dests.pop()) {
Self::dfs(next, adj, result); // use this ticket
}
result.push(cur); // post-order: no tickets left here
}
}