# Python DFS

• Attempted recursive DFS (see below in the code) but it failed due to max recursion depth exceeded. I did not pay attention to the problem description which states that n can be = 10^4. With that large n and a skewed tree test-case, recursion depth easily exceed. Changed DFS to iterative stack based to overcome that.

This problem essentially is to find if a Hamiltonian path exists in the DAG. Hamiltonian path is the path which includes all the vertices of a DAG. To find a Hamiltonian path, check the successive nodes in the topological sorted array (the input org) to see if they exists in the graph. If they do not then a Hamiltonian path does not exist and there can be multiple topological ordering.

``````class Solution(object):
def sequenceReconstruction(self, org, seqs):
"""
:type org: List[int]
:type seqs: List[List[int]]
:rtype: bool
"""
if not org or not seqs: return False
#construct graph
graph = {}
for s in seqs:
left = 0
while left <= len(s)-1:
if left == len(s)-1:
if s[left] not in graph:
graph[s[left]] = []
break
if s[left] not in graph:
graph[s[left]] = [s[left+1]]
elif s[left+1] not in graph[s[left]]:
graph[s[left]].append(s[left+1])
if s[left+1] not in graph:
graph[s[left+1]] = []
left += 1
self.isvisited = {x:0 for x in graph}
#check if a Hamiltonian path exists
self.retVal = []
left = 0
while left <= len(org)-1:
if left+1 <= len(org)-1:
if org[left] not in graph: return False
if org[left+1] not in graph[org[left]]:
return False
left +=1
#perform DFS to generate topological sorted result
stack = []
for anode in graph:
if self.isvisited[anode] == 0:
stack.append(anode)
while(stack):
node = stack[-1]
if self.isvisited[node] == 0:
self.isvisited[node] = 1
for n in graph[node]:
if self.isvisited[n] == 0:
stack.append(n)
if self.isvisited[n] == 1: return False
else:
currnode = stack.pop()
if self.isvisited[currnode] != 2:
self.retVal.append(currnode)
self.isvisited[currnode] = 2

if self.retVal[::-1] != org:
return False

#for node in graph:
#    if self.isvisited[node] == 0:
#        res = self.dfs(node, graph)
#if self.retVal[::-1] != org:
#    return False
return True

def dfs(self, node, graph):
self.isvisited[node] = 1
for n in graph[node]:
if self.isvisited[n] == 0:
res = self.dfs(n, graph)
if self.isvisited[n] == 1:
return False
self.retVal.append(node)
self.isvisited[node] = 2
return True
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.