DIY: Clone Directed Graph

Problem statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. The graph is represented using an adjacency list.

Each node in the graph contains a data (int) and a list (List[Node]) of its neighbors.

class Node {
    data = None
    neighbors = []
}

Input

The input graph will be in the form of an adjacency list. The following is an example input:

G = [[2,4],[1,3],[2,4],[1,3]]

Output

The output will be a deep copy of the input graph, and it will be in the form of an adjacency list. The following is an example output:

G` = [[2,4],[1,3],[2,4],[1,3]]

Coding exercise

Implement the clone(root_node) function, where root_node is the input’s graph starting node through which the rest of the graph can be traversed. The function returns the root node of the cloned graph.