Clone Graph – Python 3 (Week 14 – 02)

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""

class Solution:

    def cloneGraph(self, node: 'Node') -> 'Node':
        root = node
        if not node:
            return root
        
        #get all nodes
        nodes = self.getNodes(node)
        
        #creat corresponding nodes
        mapping = {}
        for node in nodes:
            mapping[node] = Node(node.val, [])
            
        
        #copy neighbors
        for node in nodes:
            #mapping[node]
            for neighbor in node.neighbors:
                new_neighbor = mapping[neighbor]
                mapping[node].neighbors.append(new_neighbor)
                
        return mapping[root] 
        
    def getNodes(self, node):
        results = {node}
        queue = collections.deque([node])
        
        while queue:
            cur = queue.popleft()
            for neighbor in cur.neighbors:
                if neighbor not in results:
                    results.add(neighbor)
                    queue.append(neighbor)
        return results