0133-clone-graph.rs

/*
Problem: LeetCode 133 - Clone Graph

Key Idea:
The key idea is to perform a depth-first traversal of the original graph while creating a new node for each node in the original graph. We'll use a hashmap to keep track of the mapping between the original nodes and their corresponding new nodes.

Approach:
1. We can approach this problem using depth-first traversal (DFS) with the help of recursion.
2. Create a HashMap to store the mapping between the original nodes and their corresponding new nodes.
3. Initialize a DFS function that takes the current node from the original graph as an argument.
4. In the DFS function:
   - Create a new node corresponding to the current node from the original graph.
   - Iterate through the neighbors of the current node.
   - For each neighbor, recursively call the DFS function to create its corresponding new node and add it to the neighbors of the new node.
   - Add the new node to the mapping in the HashMap.
5. Start the DFS from the initial node of the original graph.
6. Return the new node corresponding to the initial node as the result.

Time Complexity:
O(N + E), where N is the number of nodes in the graph, and E is the number of edges. We visit each node once and each edge once during the DFS traversal.

Space Complexity:
O(N), where N is the number of nodes in the graph. This is the space required for the HashMap and the recursion stack.
*/

// There is no option to solve this problem in Rust at the time of writing this