133. Clone Graph

 1"""
 2# Definition for a Node.
 3class Node:
 4    def __init__(self, val = 0, neighbors = None):
 5        self.val = val
 6        self.neighbors = neighbors if neighbors is not None else []
 7"""
 8
 9from typing import Optional
10
11
12class Solution:
13    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
14        # idea: given values are unique, hashmap `values: cloned_node`
15
16        if not node:
17            return None
18
19        dq = deque([node])
20        clones = {node.val: Node(node.val, [])}
21
22        while dq:
23            original = dq.popleft()
24            clone = clones[original.val]
25            clone_nei = []
26
27            for nei in original.neighbors:
28                if nei.val not in clones:
29                    clones[nei.val] = Node(nei.val, [])
30                    dq.append(nei)
31                clone_nei.append(clones[nei.val])
32            clone.neighbors = clone_nei
33
34        return clones[node.val]