Python DFS


  • 0
    B

    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
    

Log in to reply
 

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