Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

Example 1:

Input:

    1--2
    |  |
    4--3

Expected Output:

    1--2
    |  |
    4--3

Explanation: The graph has four nodes with the following connections:

• Node 1 is connected to nodes 2 and 4.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 4.
• Node 4 is connected to nodes 1 and 3.

Example 2:

Input:

    1--2
   /    \
  5      3
         |
         4

Expected Output:

    1--2
   /    \
  5      3
         |
         4

Explanation: The graph consists of five nodes with these connections:

• Node 1 is connected to nodes 2 and 5.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 4.
• Node 4 is connected to node 3.
• Node 5 is connected to node 1.

Example 3:

Input:

    1--2
   /    \
  4      3
   \    /
    5--6

Expected Output:

    1--2
   /    \
  4      3
   \    /
    5--6

Explanation: The graph has six nodes with the following connections:

• Node 1 is connected to nodes 2 and 4.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 6.
• Node 4 is connected to nodes 1 and 5.
• Node 5 is connected to nodes 4 and 6.
• Node 6 is connected to nodes 3 and 5.

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

Try it yourself

Try solving this question here: