## Approach 1: BFS

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

## C++

``````class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node)
return nullptr;

queue<Node*> q{{node}};
unordered_map<Node*, Node*> map{{node, new Node(node->val)}};

while (!q.empty()) {
Node* u = q.front();
q.pop();
for (Node* v : u->neighbors) {
if (!map.count(v)) {
map[v] = new Node(v->val);
q.push(v);
}
map[u]->neighbors.push_back(map[v]);
}
}

return map[node];
}
};
``````

## JAVA

``````class Solution {
public Node cloneGraph(Node node) {
if (node == null)
return null;

Queue<Node> q = new ArrayDeque<>(Arrays.asList(node));
Map<Node, Node> map = new HashMap<>();
map.put(node, new Node(node.val));

while (!q.isEmpty()) {
Node u = q.poll();
for (Node v : u.neighbors) {
if (!map.containsKey(v)) {
map.put(v, new Node(v.val));
q.offer(v);
}
}
}

return map.get(node);
}
}
``````

## Python

``````class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None

q = deque([node])
map = {node: Node(node.val)}

while q:
u = q.popleft()
for v in u.neighbors:
if v not in map:
map[v] = Node(v.val)
q.append(v)
map[u].neighbors.append(map[v])

return map[node]
``````

## Approach 2: DFS

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

## C++

``````class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node)
return nullptr;
if (map.count(node))
return map[node];

Node* newNode = new Node(node->val);
map[node] = newNode;

for (Node* neighbor : node->neighbors)
newNode->neighbors.push_back(cloneGraph(neighbor));

return newNode;
}

private:
unordered_map<Node*, Node*> map;
};
``````

## JAVA

``````class Solution {
public Node cloneGraph(Node node) {
if (node == null)
return null;
if (map.containsKey(node))
return map.get(node);

Node newNode = new Node(node.val);
map.put(node, newNode);

for (Node neighbor : node.neighbors)

return newNode;
}

private Map<Node, Node> map = new HashMap<>();
}
``````

## Python

``````class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None
if node in self.map:
return self.map[node]

newNode = Node(node.val, [])
self.map[node] = newNode

for neighbor in node.neighbors:
self.map[node].neighbors.append(self.cloneGraph(neighbor))

return newNode

map = {}
``````