Clone Graph — Practice

Problem

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

Each node contains a value and a list of its neighbors.

Examples

Example 1

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

Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: Deep copy of the graph.

Constraints

•The graph has at most 100 nodes.
•0 <= Node.val <= 100

Hints

Hint 1

DFS with a HashMap<original, clone> to handle cycles — check the map BEFORE recursing into a node's neighbors, so an already-cloned node is reused rather than infinitely re-cloned.

Hint 2

BFS achieves the identical result iteratively, processing nodes via a queue instead of recursion — useful specifically to avoid recursion-stack depth on a very large or deeply-connected graph.

Solutions

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> visited = new HashMap<>();
    return dfs(node, visited);
}

private Node dfs(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) return visited.get(node);
    Node clone = new Node(node.val);
    visited.put(node, clone);           // store before recursing to handle cycles
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, visited));
    }
    return clone;
}

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