Clone Graph

Given a reference node of an undirected connected graph, return a deep copy of the graph. Pattern focus: Visited set. Record already-cloned nodes in a map or set so cycles do not cause infinite recursion.

Input Format

adjList = adjacency list of an undirected graph

Output Format

deep-copied adjacency list representation

Constraints

  • 1 <= n <= 10^5
  • Graph is connected and undirected.

Examples

Example 1:

Input:

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

Output:

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

Explanation:

The cloned graph has the same adjacency structure.

Example 2:

Input:

adjList = [[2],[1]]

Output:

[[2],[1]]

Explanation:

A two-node graph is cloned with the same edges.

Example 3:

Input:

adjList = [[]]

Output:

[]

Explanation:

A single isolated node remains isolated.

Loading...
Clone Graph - Graph Traversal DSA Problem