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.

Example 1:

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class ReconstructItinerary {
    public static void main(String[] args) {
        String[][] sList = { { "MUC", "LHR" }, { "JFK", "MUC" },
         { "SFO", "SJC" }, { "LHR", "SFO" } };
        List<List<String>> mylist = new ArrayList<List<String>>();
        for (String[] list : sList) {
            mylist.add(Arrays.asList(list));
        }
        findItinerary(mylist);
        System.out.println(Arrays.asList(res));
    }

    static int size;
    static List<String> res;
    static HashMap<String, List<String>> ump;

    static List<String> findItinerary(List<List<String>> tickets) {
        res = null;
        ump = new HashMap<String, List<String>>();
        size = tickets.size() + 1;
        if (size == 1)
            return new ArrayList<>();

        for (List<String> l : tickets) {
            ump.putIfAbsent(l.get(0), new ArrayList<>());
            ump.get(l.get(0)).add(l.get(1));
        }

        for (String s : ump.keySet())
            Collections.sort(ump.get(s));

        fun("JFK", new ArrayList<String>());

        return res;
    }

    static void fun(String from, List<String> list) {
        if (res != null)
            return;
        list.add(from);
        if (list.size() == size) {
            res = new ArrayList<>(list);
            return;
        }
        int n = ump.getOrDefault(from, new ArrayList<>()).size();
        if (n == 0)
            return;
        for (int i = 0; i < n; i++) {
            if (ump.get(from).get(i).charAt(0) == '.')
                continue;
            String temp = ump.get(from).get(i);

            ump.get(from).set(i, ".");
            fun(temp, new ArrayList<>(list));
            if (res != null)
                return;
            ump.get(from).set(i, temp);
        }

    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<string> res;
map<string, multiset<string>> ump;

void fun(string x)
{
    while (ump[x].size() > 0)
    {
        auto it = ump[x].begin();
        string y = *it;
        ump[x].erase(ump[x].begin());
        fun(y);
    }
    res.push_back(x);
}
vector<string> findItinerary(vector<vector<string>> &tickets)
{
    for (int i = 0; i < tickets.size(); i++)
    {
        string u = tickets[i][0];
        string v = tickets[i][1];
        ump[u].insert(v);
    }
    fun("JFK");
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    vector<vector<string>> tickets = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
    vector<string> res = findItinerary(tickets);
    cout << "[";
    for (int i = 0; i < res.size() - 1; i++)
        cout << res[i] << ",";
    cout << res[res.size() - 1] << "]";
    return 0;
}