Clone Graph

medium graph dfs hash map

Problem

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 val (int) and a list (List[Node]) of its neighbors. class Node { public int val; public List<Node> neighbors; } Test case format: For simplicity sake, each node's value is the same as the node's index.

Walk the graph with DFS. The first time you see an original node, allocate its clone and store the pair in a map. For every neighbour, recurse to obtain (or build) its clone, then push it into the current clone's neighbour list. The map turns the graph's cycles into safe shortcuts — when DFS revisits a node, the clone is already there to wire up.

Inputadj = [[2,4],[1,3],[2,4],[1,3]]

Outputa fresh graph with the same shape

4 nodes laid out in a square; clone visits 1 → 2 → 3 → 4, wiring each pair as it returns from recursion.

adjacency (1-indexed, e.g. "2,4; 1,3; 2,4; 1,3")

def clone_graph(node):
    clones = {}
    def dfs(u):
        if u in clones:
            return clones[u]
        c = Node(u.val)
        clones[u] = c
        for v in u.neighbors:
            c.neighbors.append(dfs(v))
        return c
    return dfs(node) if node else None

function cloneGraph(node) {
  const clones = new Map();
  function dfs(u) {
    if (clones.has(u)) return clones.get(u);
    const c = { val: u.val, neighbors: [] };
    clones.set(u, c);
    for (const v of u.neighbors) c.neighbors.push(dfs(v));
    return c;
  }
  return node ? dfs(node) : null;
}

class Solution {
    Map<Node, Node> clones = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (clones.containsKey(node)) return clones.get(node);
        Node c = new Node(node.val);
        clones.put(node, c);
        for (Node v : node.neighbors) c.neighbors.add(cloneGraph(v));
        return c;
    }
}

unordered_map<Node*, Node*> clones;
Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    if (clones.count(node)) return clones[node];
    Node* c = new Node(node->val);
    clones[node] = c;
    for (Node* v : node->neighbors) c->neighbors.push_back(cloneGraph(v));
    return c;
}

Explanation

We need a deep copy of a graph: brand-new node objects wired up in the same shape. The challenge is cycles — if we naively follow neighbours, we could loop forever. The fix is a hash map that remembers each original node's clone.

We DFS from the start node. The first time we meet an original node u, we create its clone, store clones[u] = c before recursing, and then build its neighbour list by recursively cloning each neighbour.

Storing the clone first is what breaks cycles safely. When DFS later revisits u, the check if u in clones returns the already-built clone instead of making a new one, so each node is copied exactly once and every edge gets wired correctly.

Example: a 4-node square 1-2-3-4-1. We clone 1, recurse to 2, then 3, then 4; when 4 tries to reach back to 1, the map already has it, so we simply link to the existing clone and finish.

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