Clone Graph
The problem
Deep-copy the connected component reachable from a graph node. Each node has a value and a list of neighboring nodes; cycles may occur. Return null for a null input.
Example
A ↔ B must become two new nodes A′ ↔ B′, with no links into the original graph.
Need a hint?
Remember clones by original node identity before traversing edges.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Create a map from original nodes to copies. On first visit, allocate and store a copy, then populate its neighbors with recursively obtained copies. Storing before recursion breaks cycles. Equal values alone must not merge distinct nodes.
Complexity
O(V + E) time and O(V) auxiliary space, plus the copied graph.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.