Clone Graph

Statement

You are given a reference to a single node in an undirected, connected graph. Your task is to create a deep copy of the graph starting from this node. A deep copy means creating a new instance of every node in the graph with the same data and edges as the original graph, such that changes in the copied graph do not affect the original graph.

From the programming perspective, the graph is represented as an adjacency list to understand node relationships. Each node in the adjacency list corresponds to a node in the graph, and the list of neighbors describes that node’s connections. For example, for $[[2, 3], [1, 3], [1, 2]]$, there are three nodes in the graph:

$1^{st}$ node (data = $1$): Neighbors are $2^{nd}$ node (data = $2$) and $3^{rd}$ node (data = $3$).

$2^{nd}$ node (data = $2$): Neighbors are $1^{st}$ node (data = $1$) and $3^{rd}$ node (data = $3$).

$3^{rd}$ node (data = $3$): Neighbors are $1^{st}$ node (data = $1$) and $2^{nd}$ node (data = $2$).

Constraints:

• $0 \leq$ Number of nodes $\leq 100$

• $1\leq$ Node.data $\leq 100$

• Node.data is unique for each node.

• The graph is undirected, i.e., there are no self-loops or repeated edges.

• The graph is connected, i.e., any node can be visited from a given node.

Examples