Clone Graph

Given a node in a connected undirected graph, return a deep copy of the graph.

Each node in the graph contains an integer value and a list of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

The graph is shown in the test cases as an adjacency list. An adjacency list is a mapping of nodes to lists, used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

For simplicity, nodes values are numbered from 1 to n, where n is the total number of nodes in the graph. The index of each node within the adjacency list is the same as the node's value (1-indexed).

The input node will always be the first node in the graph and have 1 as the value.

There are 3 nodes in the graph.
Node 1: val = 1 and neighbors = [2].
Node 2: val = 2 and neighbors = [1, 3].
Node 3: val = 3 and neighbors = [2].

The graph has one node with no neighbors.

The graph is empty.

Approach

Use DFS with a hashmap from original nodes to cloned nodes. When visiting a node, create its clone if it doesn't exist, then recursively clone and attach all neighbors. This handles cycles by reusing already-cloned nodes.

Why It Works

Every node is cloned exactly once and stored in the map. When encountering an edge, the algorithm links the cloned nodes in the same structure as the original graph. Cycles are handled because revisiting a node returns its existing clone instead of recursing infinitely.

Complexity

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

Reference Implementation (Python)

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        clones = {}

        def dfs(n: 'Node') -> 'Node':
            if n in clones:
                return clones[n]
            copy = Node(n.val)
            clones[n] = copy
            for nei in n.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy

        return dfs(node)