# Python solution with detailed explanation

• Solution with detailed explanation https://discuss.leetcode.com/topic/76788/python-solution-with-detailed-explanation

Reconstruct Itinerary https://leetcode.com/problems/reconstruct-itinerary/

An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and ends at different vertices.

• First build a graph as a dictionary with key as vertex and value as list of edges with edge_id.
• Now the algorithm to find the Euler path is simple backtracking DFS.
• Note the Euler path may have cycles - Example 2 shows that. And Euler path allows an edge to be visited just once. Hence we will use edge_seen set to mark the edges visited. We will not mark vertices since we can visit vertices multiple times - cycles are allowed.
• We then find all the nbr,edge_id we can go to. We choose an edge that has not been visited before.
• Before we do a DFS, we add this to an edge_seen set and add to so_far
• touw - implements DFS and returns True when a path is found. We prune out search at that point.
``````class Solution(object):
def build_graph(self, tickets):
g, ticket_id = {}, 0
for trip in tickets:
v, w = trip[0], trip[1]
g.setdefault(v, [])
g[v].append((w, ticket_id))
ticket_id = ticket_id + 1
for k in g:
g[k].sort(key=lambda x:x[0])
return g

def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
g = self.build_graph(tickets)
tickets_used, itenary = set([]), ["JFK"]
self.tour(g, itenary, tickets_used, len(tickets)+1)
return itenary

def tour(self, g, itenary, tickets_used, N):
if len(itenary) == N:
return True
else:
s = itenary[-1]
if s in g:
candidates = ((nbr, ticket_id) for nbr, ticket_id in g[s] if ticket_id not in tickets_used)
for nbr, ticket_id in candidates: