332. Reconstruct Itinerary

public class Solution {
    private Dictionary<string, LinkedList<string>> flightMap = new Dictionary<string, LinkedList<string>>();
    private LinkedList<string> result = new LinkedList<string>();
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        foreach (var ticket in tickets) {
            if (!flightMap.ContainsKey(ticket[0])) {
                flightMap[ticket[0]] = new LinkedList<string>();
            }
            flightMap[ticket[0]].AddLast(ticket[1]);
        }
        foreach (var key in flightMap.Keys) {
            var sortedList = flightMap[key].OrderBy(dest => dest).ToList();
            flightMap[key] = new LinkedList<string>(sortedList);
        }
        DFS("JFK");
        return result.ToList();
    }
    private void DFS(string origin) {
        while (flightMap.ContainsKey(origin) && flightMap[origin].Count > 0) {
            var nextDest = flightMap[origin].First();
            flightMap[origin].RemoveFirst();
            DFS(nextDest);
        }
        result.AddFirst(origin);
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<string, LinkedList<string>> flightMap = new unordered_map<string, LinkedList<string>>();
    private LinkedList<string> result = new LinkedList<string>();
    public vector<string> FindItinerary(IList<vector<string>> tickets) {
        foreach (var ticket in tickets) {
            if (!flightMap.count(ticket[0])) {
                flightMap[ticket[0]] = new LinkedList<string>();
            }
            flightMap[ticket[0]].AddLast(ticket[1]);
        }
        foreach (var key in flightMap.Keys) {
            var sortedList = flightMap[key].OrderBy(dest => dest).ToList();
            flightMap[key] = new LinkedList<string>(sortedList);
        }
        DFS("JFK");
        return result.ToList();
    }
    private void DFS(string origin) {
        while (flightMap.count(origin) && flightMap[origin].size() > 0) {
            var nextDest = flightMap[origin].First();
            flightMap[origin].RemoveFirst();
            DFS(nextDest);
        }
        result.AddFirst(origin);
    }
}

class Solution {
  HashMap<String, LinkedList<String>> flightMap = new HashMap<>();
  LinkedList<String> result = null;

  public List<String> findItinerary(List<List<String>> tickets) {
    for(List<String> ticket : tickets) {
      String origin = ticket.get(0);
      String dest = ticket.get(1);
      if (this.flightMap.containsKey(origin)) {
        LinkedList<String> destList = this.flightMap.get(origin);
        destList.add(dest);
      } else {
        LinkedList<String> destList = new LinkedList<String>();
        destList.add(dest);
        this.flightMap.put(origin, destList);
      }
    }

    this.flightMap.forEach((key, value) -> Collections.sort(value));

    this.result = new LinkedList<String>();
    this.DFS("JFK");
    return this.result;
  }

  protected void DFS(String origin) {
    if (this.flightMap.containsKey(origin)) {
      LinkedList<String> destList = this.flightMap.get(origin);
      while (!destList.isEmpty()) {
        String dest = destList.pollFirst();
        DFS(dest);
      }
    }
    this.result.offerFirst(origin);
  }
}

var findItinerary = function(tickets) {
    let flightMap = new Map();
    let result = [];

    tickets.forEach(([from, to]) => {
        if (!flightMap.has(from)) flightMap.set(from, []);
        flightMap.get(from).push(to);
    });

    flightMap.forEach((value, key) => {
        value.sort();
    });

    function dfs(origin) {
        const destList = flightMap.get(origin) || [];
        while (destList.length > 0) {
            dfs(destList.shift());
        }
        result.unshift(origin);
    }

    dfs("JFK");
    return result;
};

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        flight_map = defaultdict(list)
        for origin, dest in tickets:
            flight_map[origin].append(dest)
        
        for origin in flight_map:
            flight_map[origin].sort()
        
        result = []
        self.dfs("JFK", flight_map, result)
        return result
    
    def dfs(self, origin, flight_map, result):
        dest_list = flight_map[origin]
        while dest_list:
            next_dest = dest_list.pop(0)
            self.dfs(next_dest, flight_map, result)
        result.insert(0, origin)

func findItinerary(tickets [][]string) []string {
    flightMap := make(map[string][]string)
    result := []string{}
    
    for _, ticket := range tickets {
        flightMap[ticket[0]] = append(flightMap[ticket[0]], ticket[1])
    }
    
    for key := range flightMap {
        sort.Strings(flightMap[key])
    }
    
    var dfs func(string)
    dfs = func(origin string) {
        for len(flightMap[origin]) > 0 {
            nextDest := flightMap[origin][0]
            flightMap[origin] = flightMap[origin][1:]
            dfs(nextDest)
        }
        result = append([]string{origin}, result...)
    }
    
    dfs("JFK")
    return result
}

Algorithm

Построение grafoа и сортировка:

Создайте grafo flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия.

Пройдите по всем билетам и заполните flightMap соответствующими значениями.

Отсортируйте списки аэропортов прибытия в лексикоgrafoическом порядке.

Пост-упорядоченный обход (DFS):

Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK".

Во время обхода удаляйте использованные рейсы из grafoа, чтобы не проходить по ним повторно.

Формирование маршрута:

По мере завершения обхода добавляйте текущий аэропорт в начало списка результата.

После завершения DFS return сформированный маршрут.

😎