# Clone Graph

- **Canonical ID**: `clone-graph`
- **Canonical URL**: https://dsacheatsheet.com/problems/clone-graph
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/clone-graph/

## 1. Core Invariant / The Trick

Maintain `clones = { origNode: newNode }` *before* recursing into neighbors so cycles short-circuit immediately to the already allocated copy without infinite loops.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(V + E)`
- **Space Complexity**: `O(V)`
- **Proof**: Visits each node once and traverses each edge once per endpoint.

## 3. Minimal Idiomatic Code

### Python
```python
def cloneGraph(node: Optional[Node]) -> Optional[Node]:
    if not node:
        return None
    clones = {}
    def dfs(u: Node) -> Node:
        if u in clones:
            return clones[u]
        copy = Node(u.val)
        clones[u] = copy
        for nbr in u.neighbors:
            copy.neighbors.append(dfs(nbr))
        return copy
    return dfs(node)
```

### TypeScript
```typescript
export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>();
  const dfs = (u: Node): Node => {
    if (clones.has(u)) return clones.get(u)!;
    const copy = new Node(u.val);
    clones.set(u, copy);
    for (const nbr of u.neighbors) copy.neighbors.push(dfs(nbr));
    return copy;
  };
  return dfs(node);
}
```

### C++
```cpp
Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> clones;
    auto dfs = [&](auto& self, Node* u) -> Node* {
        if (clones.count(u)) return clones[u];
        Node* copy = new Node(u->val);
        clones[u] = copy;
        for (Node* nbr : u->neighbors) copy->neighbors.push_back(self(self, nbr));
        return copy;
    };
    return dfs(dfs, node);
}
```

### Java
```java
Map<Node, Node> clones = new HashMap<>();
Node cloneGraph(Node node) {
    if (node == null) return null;
    if (clones.containsKey(node)) return clones.get(node);
    Node copy = new Node(node.val);
    clones.put(node, copy);
    for (Node nbr : node.neighbors) copy.neighbors.add(cloneGraph(nbr));
    return copy;
}
```

### Go
```go
func cloneGraph(node *Node) *Node {
    if node == nil { return nil }
    clones := map[*Node]*Node{}
    var dfs func(*Node) *Node
    dfs = func(u *Node) *Node {
        if c, ok := clones[u]; ok { return c }
        c := &Node{Val: u.Val}
        clones[u] = c
        for _, nbr := range u.Neighbors { c.Neighbors = append(c.Neighbors, dfs(nbr)) }
        return c
    }
    return dfs(node)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Registering the clone *after* neighbor DFS causes infinite recursion on cycles.
- Failing to handle `node is None` input crashes on empty graph.

### Follow-ups
- Copy List with Random Pointer uses the identical `{ origNode: cloneNode }` bijection trick.