def clone_graph(node):
if not node:
return None
visited = {}
def dfs(cur):
if cur in visited:
return visited[cur]
clone = Node(cur.val)
visited[cur] = clone
for nb in cur.neighbors:
clone.neighbors.append(dfs(nb))
return clone
return dfs(node)Variables
v- number of vertices (graph nodes)e- number of edges
Explanation
Each vertex is cloned once and each edge is traversed once (twice in an undirected graph, still O(e)) - total time **O(V + E)**. The visited map holds one entry per vertex; the recursion stack is bounded by the longest path, also at most `V` - **O(V)** auxiliary.