Given a reference to a node in a connected undirected graph, return a deep copy: every node cloned, every edge reproduced, no node duplicated. Nodes carry a value and a neighbours list.
Using a hashmap from original-node → clone as BOTH the visited set and the lookup that stops cycles from causing infinite recursion.
Deep-copying a graph is a traversal (DFS or BFS) whose crucial extra ingredient is a map from each original node to its clone. That single map does two jobs: it tells you whether a node has already been cloned (so cycles and shared neighbours don't spin forever or duplicate), and it lets you wire cloned neighbours by looking up each original neighbour's clone. The recipe: on visiting a node, if it's in the map return its clone; otherwise create the clone, put it in the map BEFORE recursing (order matters — this is what breaks cycles), then for each neighbour recurse and push the returned clone into the copy's neighbour list. Recognition signal: 'deep copy / clone a linked structure with cycles or shared references' → traverse while memoising original→copy in a map. The same map pattern clones a linked list with random pointers.
Deep-copying any graph or linked structure that may contain cycles or shared nodes → DFS/BFS with a Map from original node to its clone, populated before recursing.
Time O(V + E) · Space O(V)