```
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
graph = self.buildGraph(tickets)
path = []
path.append("JFK")
self.dfs(graph, path, tickets)
return path
def dfs(self, graph, path, tickets):
to = graph[path[-1]]
to.sort()
for i in range(len(to)):
d = to.pop(i)
path.append(d)
self.dfs(graph, path, tickets)
if len(path) == len(tickets) + 1:
return
path.pop()
to.insert(i,d)
return
def buildGraph(self, tickets):
graph = dict()
for ticket in tickets:
if ticket[0] in graph:
graph[ticket[0]].append(ticket[1])
else:
graph[ticket[0]] = [ticket[1]]
if ticket[1] not in graph:
graph[ticket[1]] = []
return graph
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
graph = self.buildGraph(tickets)
path = []
path.append("JFK")
self.dfs(graph, path, tickets)
return path
def dfs(self, graph, path, tickets):
dq = graph[path[-1]]
count = len(dq)
while count > 0:
count -= 1
path.append(dq.popleft())
self.dfs(graph, path, tickets)
if len(path) == len(tickets) + 1:
return
dq.append(path.pop())
return
def buildGraph(self, tickets):
graph = dict()
for ticket in tickets:
if ticket[0] in graph:
graph[ticket[0]].append(ticket[1])
else:
graph[ticket[0]] = [ticket[1]]
if ticket[1] not in graph:
graph[ticket[1]] = []
for d in graph:
temp = graph[d]
temp.sort()
graph[d] = collections.deque(temp)
return graph
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
graph = self.buildDigraph(tickets)
result = []
stack = ["JFK"]
while len(stack) != 0:
u = stack[-1]
adj = graph[u]
adj.sort()
adj.reverse()
if len(adj) == 0:
result.append(stack.pop())
else:
stack.append(adj.pop())
result.reverse()
return result
def buildDigraph(self, arcs):
graph = {}
for arc in arcs:
if arc[0] in graph:
graph[arc[0]].append(arc[1])
else:
graph[arc[0]] = [arc[1]]
if arc[1] not in graph:
graph[arc[1]] = []
return graph
```