Solutions

# The graph can have cycles, so we keep track of what we visited already. We can use either BFS or DFS to traverse the graph and create a copy of it.
# graphs


# BFS - O(V + E) time, O(V) space
def cloneGraph(node: Optional['Node']) -> Optional['Node']:
    if not node:
        return None

    from collections import deque

    h = {}

    q = deque()
    q.append(node)
    h[node] = Node(node.val)

    while q:
        cur = q.popleft()

        for ne in cur.neighbors:
            if ne not in h:
                h[ne] = Node(ne.val)
                q.append(ne)
            h[cur].neighbors.append(h[ne])

    return h[node]


# DFS - O(V + E) time, O(V) space
def cloneGraphdfs(node: Optional['Node']) -> Optional['Node']:
    # The graph can contain cycles, so we keep track of what we visited already
    h = {}

    def dfs(node: Node):
        if node in h:
            return h[node]

        newnode = Node(node.val, [])
        h[node] = newnode
        for ne in node.neighbors:
            newnode.neighbors.append(dfs(ne))
        return newnode

    return dfs(node) if node else None