LC133. Clone Graph

Approach 1: Breadth-First Search

"""
# 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
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node: return None
 
        q = deque([node])
        cloneMap = {}
 
        while q:
            node = q.popleft()
 
            if node.val not in cloneMap:
                cloneMap[node.val] = Node(node.val, [])
 
            for nei in node.neighbors:
                if nei.val not in cloneMap:
                    q.append(nei)
                    cloneMap[nei.val] = Node(nei.val, [])
 
                cloneMap[node.val].neighbors.append(
                    cloneMap[nei.val]
                )
        
        return cloneMap[1]

Complexity

Time: $O(n)$
Space: $O(n)$

Other Languages