1. Problem Statement

You’re given a reference to a node in a connected, undirected graph. Each node contains:

• An integer value val
• A list of its neighbors: List<Node> neighbors

You must return a deep copy of the entire graph.

2. Node Definition

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

    public Node() {
        neighbors = new ArrayList<>();
    }

    public Node(int val) {
        this.val = val;
        neighbors = new ArrayList<>();
    }

    public Node(int val, List<Node> neighbors) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

3. Key Idea

This is a classic graph traversal + cloning problem.

When you encounter a node:

• If it hasn’t been cloned yet → create a copy and store it in a map.
• Then recursively or iteratively visit and clone each of its neighbors.

4. DFS Approach with HashMap

We use a Map<Node, Node> to track already cloned nodes and prevent infinite loops.

5. Java Solution: DFS

import java.util.*;

public class CloneGraph {

    private Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;

        // If node is already cloned, return the clone
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Clone the current node
        Node clone = new Node(node.val);
        visited.put(node, clone);

        // Clone all neighbors
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }

        return clone;
    }
}

6. Time and Space Complexity

• Time Complexity: O(N + E),
  where N = number of nodes, E = number of edges
• Space Complexity: O(N),
  for the visited map and recursion stack