Reconstruct Itinerary
Intuition
Solution
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
airports = sorted(list(set([t[0] for t in tickets] + [t[1] for t in tickets])))
tickets.sort()
size = len(airports)
indexes = {}
for i, name in enumerate(airports):
indexes[name] = i
graph = DiGraph(size)
for p, q in tickets:
graph.add_edge(indexes[p], indexes[q])
self.postorder = []
self.dfs(graph, indexes['JFK'])
return [airports[i] for i in self.postorder[::-1]]
def dfs(self, graph, vertex):
for i, child in enumerate(graph.adj[vertex]):
if not graph.used[vertex][i]:
graph.used[vertex][i] = True
self.dfs(graph, child)
self.postorder.append(vertex)