Clone Graph

medium

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list of its neighbors.

For simplicity, each node's value is the same as the node's index (1-indexed). The graph is represented using an adjacency list in the test cases.

Test Cases

Copy an input into the main harness and Run to verify

Input

adjList = [[2,4],[1,3],[2,4],[1,3]]

Expected Output

[[2,4],[1,3],[2,4],[1,3]]

Explanation: The cloned graph has the same structure with brand new node objects.

Input

adjList = [[]]

Expected Output

[[]]

Input

adjList = []

Expected Output

[]

Constraints

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops.
The Graph is connected.

Hints

Hint 1 — click to reveal

A hash map from original node -> clone prevents infinite loops on cycles.

Hint 2 — click to reveal

BFS or DFS both work; clone neighbors lazily.

Java Compiler