96. Clone Graph
Clone the portion of the graph reachable from the supplied root. Preserve node values and the ordered neighbor lists, including repeated neighbor occurrences.
Each original node needs exactly one corresponding copied node. Cycles, self-loops, and parallel edges must remain valid without references pointing back to original objects.
Example 1
Input
values=[7,7,9], edges=[[0,1,1],[2],[0]], root=0
Output
three fresh nodes with the same ordered edge lists
Explanation: Root self-loop points to its own copy; both parallel edges point to the one copy of node 1, despite repeated value 7.
Example 2
Input
values=[1,2,1,3], edges=[[1],[0],[2,3],[]], root=2
Output
copies of original nodes 2 and 3 only
Explanation: The disconnected 0↔1 component must not be copied.
Constraints
0 <= reachable nodes <= 1050 <= neighbor occurrences <= 2 * 105-231 <= node.value <= 231 - 1- Neighbor entries are non-null. Directed edges, repeated edges and cycles are permitted.
Hints
Hint 1
What should a back edge point to while a graph is being constructed?
Hint 2
You need one registered copy per original object before exploring its edges.
Hint 3
Traverse originals, allocate missing neighbor copies, and append mapped references for every list slot.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Self-loop, duplicate values, and parallel occurrences
[7,7,9]
[[0,1,1],[2],[0]]
0
{"root":"C0","nodes":[{"id":"C0","value":7,"neighbors":["C0","C1","C1"]},{"id":"C1","value":7,"neighbors":["C2"]},{"id":"C2","value":9,"neighbors":["C0"]}]}