Clone a Directed Graph

Statement

Given the root node of a directed graph, clone this graph by creating its deep copy, such that the cloned graph has the same vertices and edges as the original graph.

Example

Let’s look at the graphs below as an example. If the input graph is $G = (V, E)$ where $V$ is a set of vertices and $E$ is a set of edges, then the output graph (the cloned graph) is $G' = (V', E')$ such that $V = V'$ and $E = E'$.