Deep Clone a Graph

medium graph dfs hash map

Problem

You're given a reference to a node in a connected undirected graph. Return a deep copy: every node is freshly created and the new graph mirrors the neighbour relationships of the original without sharing any objects.

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(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 clone(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;
}

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