31 lines
865 B
Python
31 lines
865 B
Python
|
|
# Definition for a Node.
|
|
class Node:
|
|
def __init__(self, val = 0, neighbors = None):
|
|
self.val = val
|
|
self.neighbors = neighbors if neighbors is not None else []
|
|
|
|
|
|
from typing import Optional
|
|
from collections import deque
|
|
|
|
class Solution:
|
|
def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
|
|
if not node:
|
|
return None
|
|
|
|
graph_map = {}
|
|
q = deque()
|
|
q.append(node)
|
|
root = Node(node.val)
|
|
graph_map[node.val] = root
|
|
|
|
while q:
|
|
cur_node = q.popleft()
|
|
for neighbor in cur_node.neighbors:
|
|
if neighbor.val not in graph_map:
|
|
graph_map[neighbor.val] = Node(val=neighbor.val)
|
|
q.append(neighbor)
|
|
graph_map[cur_node.val].neighbors.append(graph_map[neighbor.val])
|
|
|
|
return root |