Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

LeetCode: Clone Graph

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Example:

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

Graph:
  1 --- 2
  |     |
  4 --- 3

Output: [[2,4],[1,3],[2,4],[1,3]]
(A deep copy of the input graph)

Hints

Hint 1

You need to keep track of which nodes you've already cloned to avoid infinite loops. Think about what data structure helps with that.

Hint 2

Use a hash map to map original nodes to their clones. This serves two purposes: avoiding duplicates and handling cycles.

Hint 3

Add the node to your map BEFORE processing its neighbors. This prevents infinite recursion when there are cycles.