Clone Graph

MediumGraphs

Return a deep copy of a connected undirected graph given a reference to one of its nodes.

Constraints

0 <= nodes <= 100
No repeated edges, no self-loops

DFS with a visited map

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

Recursively clone nodes, storing original-to-clone mappings so each node is created once. For each neighbor, clone it (or reuse the cached clone) and link it.

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
};

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> seen;
    function<Node*(Node*)> dfs = [&](Node* n) -> Node* {
        if (seen.count(n)) return seen[n];
        Node* copy = new Node();
        copy->val = n->val;
        seen[n] = copy;
        for (Node* nb : n->neighbors) copy->neighbors.push_back(dfs(nb));
        return copy;
    };
    return dfs(node);
}