clone graph

"""
Definition for a undirected graph node
class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""
import collections

class :
    """
    @param: node: A undirected graph node
    @return: A undirected graph node
    """
    def cloneGraph(self, node):
        
        if not node:
            return None
        
        nodes = self.getNodes(node)
        
        node_dict = {}
        for i in nodes:
            node_dict[i] = UndirectedGraphNode(i.label)
        
        for i in nodes:
            for j in i.neighbors:
                node_dict[i].neighbors.append(node_dict[j])
        
        return node_dict[node]
        
        
    
    def getNodes(self, node):
        result = set([node])
        queue = collections.deque()
        queue.append(node)
        while len(queue):
            head = queue.popleft()
            for i in head.neighbors:
                if i not in result:
                    result.add(i)
                    queue.append(i)
        return result