Clone Graph

Given a reference of 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 of its neighbors.

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

Test case format:

• The graph is represented as an adjacency list
• Each element is a list of neighbors for the node at that index (1-indexed)
• The first element's neighbors define node 1's connections, etc.

Example Graph:

1 --- 2
|     |
4 --- 3

Adjacency list: [[2,4],[1,3],[2,4],[1,3]]

DFS Approach:

1. Create a hashmap to store {original node -> cloned node}
2. For each node, create its clone if not already created
3. Recursively clone all neighbors
4. Connect the cloned node to its cloned neighbors

Key Insight: The hashmap serves two purposes:

• Tracks visited nodes to avoid infinite loops in cyclic graphs
• Maps original to clone for building connections