Clone Graph
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph.
Each node contains:
val
neighbors
The graph may contain cycles, so simply copying each node once is not enough. We need to make sure every original node gets exactly one cloned node.
Example Graph:
1
/ \
2---4
\ /
3
If we clone this graph, the cloned nodes must have the same connections:
1'
/ \
2'---4'
\ /
3'
The cloned graph must be completely independent of the original graph.
Main Idea
Use DFS or BFS + HashMap.
The HashMap stores:
Original Node → Cloned Node
For example:
1 → 1'
2 → 2'
3 → 3'
4 → 4'
When we encounter a node:
- If it is already cloned, return the existing clone.
- Otherwise, create a new clone.
- Store it in the HashMap.
- Clone all its neighbors.
The HashMap is especially important for handling cycles.
Example 1
Input
4 2 2 4 2 1 3 2 2 4 2 1 3
Output
1: 2 4 2: 1 3 3: 2 4 4: 1 3
Explanation
The original graph is:
1
/ \
2 4
\ /
3
Every node is cloned exactly once.
The connections are also preserved:
1 → 2,4
2 → 1,3
3 → 2,4
4 → 1,3
The cloned graph therefore has the same structure, but all nodes are new objects.
Example 2
Input
1 0
Output
1:
Explanation
The graph contains only one node and it has no neighbors.
Therefore, the clone also contains one independent node with no neighbors.
Constraints
Hints:
Hint 1
You need to create a new node for every original node.
Hint 2
Use a HashMap:
Original Node → Cloned Node
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 15, 2026
Last updated
Aug 15, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output