Create a deep copy of an undirected graph starting from a given node.
Clone Graph
You are given a reference to a node in a connected undirected graph. Each node has a value and a list of its neighboring nodes.
Return a deep copy of the graph starting from that node. The cloned graph should contain new nodes with the same values and the same neighbor relationships, but none of the original nodes should be reused.
If the given node is empty, return an empty result.
Input Format
- A reference to a graph node
node. - Each node contains:
- an integer value
- a list of neighboring nodes
Output Format
Return a reference to the cloned node corresponding to the input node.
Constraints
- The graph may contain cycles.
- The graph is connected.
- You must create a deep copy; do not reuse original nodes.
- Node values may not be unique.
Example 1
Input
node = 1 1: [2,4] 2: [1,3] 3: [2,4] 4: [1,3]
Output
A cloned graph whose starting node has value 1 and the same adjacency relationships.
Explanation
The clone should contain four newly created nodes. The neighbor structure matches the original graph, but every node in the result is a distinct object.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.