Python DFS short solution


  • 22
    A

    Use a dictionary to store the UndirectedGraphNode

    def cloneGraph(self, node):
        if not node:
            return node
        root = UndirectedGraphNode(node.label)
        stack = [node]
        visit = {}
        visit[node.label] = root
        while stack:
            top = stack.pop()
        
            for n in top.neighbors:
                if n.label not in visit:
                    stack.append(n)
                    visit[n.label] = UndirectedGraphNode(n.label)
                visit[top.label].neighbors.append(visit[n.label])
        
        return root

  • 0
    H

    What is the running time for this?


  • 5
    G

    Converted your idea into recursive solution:

    class Solution(object):
        def __init__(self):
            self.visited = {}
            
        def cloneGraph(self, node):
            if not node:
                return None
            if node.label in self.visited:
                return self.visited[node.label]
    
            clone = UndirectedGraphNode(node.label)
            self.visited[node.label] = clone
                
            for n in node.neighbors:
                clone.neighbors.append(self.cloneGraph(n))
            return clone

  • 1
    E

    @autekwing is this solution using DFS? it seems like you are doing BFS since you visit and take care of top's neighbors first and then move on


  • 1
    V

    @ericakimnh It looks like BSF, but he's actually popping from the end of the list, not the head, which makes it DFS. At first I thought it BSF too :)


Log in to reply
 

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