Clone Graph

The key idea

Visit each node once and keep a map from each original node to its clone. The map both records work already done (so shared neighbors and cycles are not copied twice) and lets you wire the clone's neighbor links to the already-created copies.

Problem

You are given a reference to 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 (List[Node]) of its neighbors.

The graph is shown using an adjacency list. An adjacency list is a collection of unordered lists, one for each node. The i-th list describes the neighbors of the node with value i + 1 (the nodes are 1-indexed).

The given node is always the first node with value 1. You must return the copy of the given node as a reference to the cloned graph. The clone must contain brand-new nodes — none of the returned nodes may be the same object as a node in the input.

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 in the graph.
The graph is connected and all nodes can be visited starting from the given node.

Examples

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]

Input: adjList = [[2],[1]] Output: [[2],[1]]

Input: adjList = [[]] Output: [[]]

Complexity

Time: O(V + E) Space: O(V)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →