# 133. Clone Graph

Reference: LeetCode

Difficulty: Medium

## Problem

Given a reference of a node in a

`connected undirected graph`

, return adeep copy (clone)of the graph. Each node in the graph contains a val (`int`

) and a list (`List[Node]`

) of its neighbors.

**Note:**

- The number of nodes will be between
`1`

and`100`

. - The undirected graph is a
`simple graph`

, which means no repeated edges and no self-loops in the graph. - Since the graph is undirected, if node
`p`

has node`q`

as neighbor, then node`q`

must have node`p`

as neighbor too. - You must return the
**copy of the given node**as a reference to the cloned graph.

## Analysis

### DFS (recursion)

1 | public Node cloneGraph(Node node) { |

**Optimization:** We can combine `dfsSetMap`

and `dfsSetNeighbors`

to get clean code!

1 | private void dfs(Node node, Map<Node, Node> map) { |

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

Comment