LeetCode-Python-133. クローン図

連通図のノードへの参照がない場合は、図の深いコピー(クローン)を返します.図中の各ノードには、その値val(Int)とその隣のリスト(list[Node])が含まれています.
例:
入力:{「$id」:「$id」:「"1」、「neighbors」:[{「$id」:「$id」:「{2」、「neighbors」:[{「$ref」:[{「$ ref」:「$ id」:「"3」、「neighbors」:[{「$ref」:「「$ ref」:「「$ 2」},{「$id」:「「$id」:「「{4」、「neighbors」:[{「$ref」:「「$ 3」},{「$ref」:「「$ref」:「}」,「$ref」」:「「}」」:「}」,「val」:4}],「val」:3}],「val」:「「}val":2},{"$ref":"4"},"val":1}
説明:ノード1の値は1で、ノード2と4の2つの隣接があります.ノード2の値は2で、ノード1と3の2つの隣接があります.ノード3の値は3で、ノード2と4の2つの隣接があります.ノード4の値は4で、ノード1と3の2つの隣接があります. 
ヒント:
ノード数は1～100です.無方向図は単純な図であり、これは図中に重複するエッジも自己ループもないことを意味する.図は無方向であるため、ノードpがノードqの隣接である場合、ノードqもノードpの隣接である必要がある.指定したノードのコピーをクローンマップの参照として返す必要があります.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/clone-graph著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
図の遍歴BFS+ハッシュ表解題.
ハッシュテーブルmappingを使用して、すべてのノードとそのcopyの関係を記録します.
時間複雑度:O(N)
空間複雑度:O(N)

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        from collections import defaultdict, deque
        mapping = dict() # key is the original node, value is its copy
        
        queue = deque([node])
        visited = set()
        visited.add(node)
        while queue:
            cur = queue.popleft()
            visited.add(cur)

            copy = Node(cur.val, [])
            mapping[cur] = copy
            for neigh in cur.neighbors:
                if neigh not in visited:
                    queue.append(neigh)
                    
        for cur, copy in mapping.items():
            for each in cur.neighbors:
                copy.neighbors.append(mapping[each])
        return mapping[node]