Python solution with BFS, 120ms


  • 0
    A
    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            if node is None:
                return
    
            hs = {}
            que = [node]
    
            while que:
                nd = que.pop(0)
                if not hs.has_key(nd.label):
                    res1 = UndirectedGraphNode(nd.label)
                    hs[nd.label] = res1
                else:
                    res1 = hs[nd.label]
    
                for i in nd.neighbors:
                    if not hs.has_key(i.label):
                        que.append(i)
                        temp = UndirectedGraphNode(i.label)
                        hs[temp.label] = temp
                        res1.neighbors.append(temp)
                    else:
                        res1.neighbors.append(hs[i.label])
    
            return hs[node.label]

  • 0
    C

    Good solution, it seems better to use deque instead of queue (list) in this case:

    def cloneGraph(self, node):
        if not node:
            return None
        dic, queue = dict(), collections.deque([node])
        while queue:
            curr = queue.popleft()
            if curr.label not in dic:
                newNode = UndirectedGraphNode(curr.label)
                dic[curr.label] = newNode
            else:
                newNode = dic[curr.label]
                
            for neighbor in curr.neighbors:
                if neighbor.label not in dic:
                    queue.append(neighbor)
                    tmp = UndirectedGraphNode(neighbor.label)
                    dic[tmp.label] = tmp
                    newNode.neighbors.append(tmp)
                else:
                    newNode.neighbors.append(dic[neighbor.label])
        return dic[node.label]

Log in to reply
 

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