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.

Note:


       If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
       All airports are represented by three capital letters (IATA code).
       You may assume all tickets form at least one valid itinerary.


Example 1:


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


Example 2:


Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.


Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Paths and circuits

Graph traversal

Graph algorithms

Starter code: class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        

Solutions:
class Solution:

	def findItinerary(self, tickets):
		dict = collections.defaultdict(list)
		for flight in sorted(tickets)[::-1]:
			dict[flight[0]].append(flight[1])
		res = collections.deque()

		def visit(s):
			while dict[s]:
				visit(dict[s].pop())
			res.appendleft(s)
		visit('JFK')
		return list(res)


class Solution:

	def findItinerary(self, tickets):
		targets = collections.defaultdict(list)
		for (a, b) in sorted(tickets, reverse=True):
			targets[a] += [b]
		(route, stack) = ([], ['JFK'])
		while stack:
			while targets[stack[-1]]:
				stack += [targets[stack[-1]].pop()]
			route += [stack.pop()]
		return route[::-1]


class Solution:

	def findItinerary(self, tickets):
		graph = {}
		for line in tickets:
			if line[0] not in graph:
				graph[line[0]] = [line[1]]
			else:
				graph[line[0]].append(line[1])
		for key in graph:
			graph[key] = sorted(graph[key], reverse=True)
		res = []
		cur = 'JFK'
		stack = []
		for i in range(len(tickets)):
			while cur not in graph or not graph[cur]:
				stack.append(cur)
				cur = res.pop()
			res.append(cur)
			cur = graph[cur].pop()
		res.append(cur)
		while stack:
			res.append(stack.pop())
		return res


class Solution:

	def findItinerary(self, tickets):
		tickets.sort()
		schedule = {}
		for ticket in reversed(tickets):
			schedule[ticket[0]] = schedule[ticket[0]] + [ticket[1]] if ticket[0] in schedule else [ticket[1]]
		return list(reversed(self.fly(schedule, 'JFK')))

	def fly(self, schedule, depart):
		route = []
		while depart in schedule and len(schedule[depart]) > 0:
			route += self.fly(schedule, schedule[depart].pop())
		route += [depart]
		return route


class Solution:

	def findItinerary(self, tickets):
		self.hasmap = {}
		for ticket in tickets:
			self.hasmap.setdefault(ticket[0], []).append(ticket[1])
		self.route = ['JFK']
		return self.dfs('JFK', tickets)

	def dfs(self, start_airport, tickets):
		if len(self.route) == len(tickets) + 1:
			return self.route
		dests = self.hasmap.get(start_airport)
		if dests is not None:
			for dest in sorted(dests):
				self.hasmap[start_airport].remove(dest)
				self.route.append(dest)
				work = self.dfs(dest, tickets)
				if work:
					return self.route
				self.route.pop()
				self.hasmap[start_airport].append(dest)


class Solution:

	def findItinerary(self, tickets):
		d = collections.defaultdict(list)
		tickets.sort(key=operator.itemgetter(1))
		for (src, dst) in tickets:
			d[src].append([dst, False])
		ans = []

		def DFS(src):
			ans.append(src)
			if len(ans) == len(tickets) + 1:
				return True
			for (i, a) in enumerate(d[src]):
				if not a[1]:
					d[src][i][1] = True
					if DFS(a[0]):
						return True
					d[src][i][1] = False
			ans.pop()
			return False
		DFS('JFK')
		return ans


class Solution(object):

	def __init__(self):
		self.res = []

	def findItinerary(self, tickets):
		if tickets is None or len(tickets) == 0:
			return []
		dic = {}
		dic_city = {}
		for t in tickets:
			if (t[0], t[1]) not in dic:
				dic[t[0], t[1]] = 0
			dic[t[0], t[1]] += 1
			if t[0] not in dic_city:
				dic_city[t[0]] = []
			dic_city[t[0]].append(t[1])
		for k in dic_city.keys():
			dic_city[k] = set(dic_city[k])
			dic_city[k] = list(dic_city[k])
			dic_city[k].sort()
		self.res = []
		self.dfs('JFK', dic, dic_city, ['JFK'], len(tickets) + 1)
		return self.res

	def dfs(self, city, dic, dic_city, cur, tar):
		if len(cur) == tar:
			if not self.res:
				self.res = list(cur)
			return True
		if city in dic_city:
			citys = dic_city[city]
			for c in citys:
				if (city, c) in dic and dic[city, c] > 0:
					dic[city, c] -= 1
					cur.append(c)
					if self.dfs(c, dic, dic_city, cur, tar):
						return True
					cur.pop()
					dic[city, c] += 1
		return False


class Solution:

	def findItinerary(self, tickets):
		d = collections.defaultdict(list)
		tickets.sort()
		for (i, j) in tickets:
			d[i] += [j]

		def dfs(path, start):
			path += [start]
			if len(path) == length:
				return True
			i = 0
			while i < len(d[start]):
				next = d[start].pop(0)
				print((next, d[start]))
				i += 1
				if dfs(path, next):
					return True
				d[start] += [next]
			path.pop()
			return False
		(path, length) = ([], len(tickets) + 1)
		dfs(path, 'JFK')
		return path