Reconstruct Itinerary

class Solution {
    private List<String> route;
    private Map<String, List<Integer>> out;
    private List<List<String>> t;
    private boolean[] used;

    public List<String> findItinerary(List<List<String>> tickets) {
        t = new ArrayList<>(tickets);
        t.sort((a, b) -> a.get(1).compareTo(b.get(1)));
        out = new HashMap<>();
        for (int i = 0; i < t.size(); i++)
            out.computeIfAbsent(t.get(i).get(0), x -> new ArrayList<>()).add(i);
        used = new boolean[t.size()];
        route = new ArrayList<>();
        route.add("JFK");
        dfs("JFK");
        return route;
    }

    private boolean dfs(String at) {
        if (route.size() == t.size() + 1) return true;
        for (int i : out.getOrDefault(at, Collections.emptyList())) {
            if (used[i]) continue;
            used[i] = true;
            route.add(t.get(i).get(1));
            if (dfs(t.get(i).get(1))) return true;
            route.remove(route.size() - 1);
            used[i] = false;
        }
        return false;
    }
}

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        t = sorted(tickets, key=lambda x: x[1])
        out = {}
        for i, (a, _) in enumerate(t):
            out.setdefault(a, []).append(i)
        used = [False] * len(t)
        route = ["JFK"]

        def dfs(at: str) -> bool:
            if len(route) == len(t) + 1:
                return True
            for i in out.get(at, []):
                if used[i]:
                    continue
                used[i] = True
                route.append(t[i][1])
                if dfs(t[i][1]):
                    return True
                route.pop()
                used[i] = False
            return False

        dfs("JFK")
        return route

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        t = tickets;
        stable_sort(t.begin(), t.end(), [](const vector<string>& a, const vector<string>& b) { return a[1] < b[1]; });
        for (int i = 0; i < (int)t.size(); i++) out[t[i][0]].push_back(i);
        used.assign(t.size(), false);
        route = {"JFK"};
        dfs("JFK");
        return route;
    }

private:
    vector<vector<string>> t;
    unordered_map<string, vector<int>> out;
    vector<bool> used;
    vector<string> route;

    bool dfs(const string& at) {
        if (route.size() == t.size() + 1) return true;
        auto it = out.find(at);
        if (it == out.end()) return false;
        for (int i : it->second) {
            if (used[i]) continue;
            used[i] = true;
            route.push_back(t[i][1]);
            if (dfs(t[i][1])) return true;
            route.pop_back();
            used[i] = false;
        }
        return false;
    }
};

function findItinerary(tickets) {
    const t = tickets.slice().sort((a, b) => (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0));
    const out = new Map();
    t.forEach(([a], i) => {
        if (!out.has(a)) out.set(a, []);
        out.get(a).push(i);
    });
    const used = new Array(t.length).fill(false);
    const route = ["JFK"];
    function dfs(at) {
        if (route.length === t.length + 1) return true;
        for (const i of out.get(at) || []) {
            if (used[i]) continue;
            used[i] = true;
            route.push(t[i][1]);
            if (dfs(t[i][1])) return true;
            route.pop();
            used[i] = false;
        }
        return false;
    }
    dfs("JFK");
    return route;
}

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> out = new HashMap<>();
        for (List<String> tk : tickets)
            out.computeIfAbsent(tk.get(0), x -> new ArrayList<>()).add(tk.get(1));
        for (List<String> l : out.values()) l.sort(Collections.reverseOrder());
        Deque<String> stack = new ArrayDeque<>();
        List<String> route = new ArrayList<>();
        stack.push("JFK");
        while (!stack.isEmpty()) {
            List<String> next = out.get(stack.peek());
            if (next != null && !next.isEmpty()) stack.push(next.remove(next.size() - 1));
            else route.add(stack.pop());
        }
        Collections.reverse(route);
        return route;
    }
}

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        out = {}
        for a, b in tickets:
            out.setdefault(a, []).append(b)
        for lst in out.values():
            lst.sort(reverse=True)
        stack = ["JFK"]
        route = []
        while stack:
            nxt = out.get(stack[-1])
            if nxt:
                stack.append(nxt.pop())
            else:
                route.append(stack.pop())
        return route[::-1]

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> out;
        for (auto& tk : tickets) out[tk[0]].push_back(tk[1]);
        for (auto& p : out) sort(p.second.rbegin(), p.second.rend());
        vector<string> stack = {"JFK"}, route;
        while (!stack.empty()) {
            auto it = out.find(stack.back());
            if (it != out.end() && !it->second.empty()) {
                string nxt = it->second.back();
                it->second.pop_back();
                stack.push_back(nxt);
            } else {
                route.push_back(stack.back());
                stack.pop_back();
            }
        }
        reverse(route.begin(), route.end());
        return route;
    }
};

function findItinerary(tickets) {
    const out = new Map();
    for (const [a, b] of tickets) {
        if (!out.has(a)) out.set(a, []);
        out.get(a).push(b);
    }
    for (const lst of out.values()) lst.sort().reverse();
    const stack = ["JFK"];
    const route = [];
    while (stack.length > 0) {
        const nxt = out.get(stack[stack.length - 1]);
        if (nxt && nxt.length > 0) stack.push(nxt.pop());
        else route.push(stack.pop());
    }
    return route.reverse();
}