Here's the complete implementation:
function cloneGraph(node):
if node is null:
return null
old_to_new = empty map
function dfs(original):
if original in old_to_new:
return old_to_new[original]
copy = new Node(original.val)
old_to_new[original] = copy
for each neighbor in original.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
return dfs(node)
Time: where N is nodes and E is edges. Space: for the map and recursion stack.