Clone a graph
A graph is a set of nodes, some of them joined in pairs by edges. You receive one node of a connected, undirected graph. Each node is a Node with two fields: val, a whole number, and neighbors, the list of nodes it shares an edge with. Connected means you can get from any node to any other by following edges. Undirected means every edge shows up in both lists: if node 2 is in node 1's neighbors, then node 1 is in node 2's.
Return a deep copy of the graph: a brand new Node for every node, with the same val, whose neighbors list holds the copies of the original neighbors in the same order. No original node may appear anywhere in the copy. Return the copy of the node you were given, or None if you were given None (an empty graph).
The values are 1 to n, each used once. The examples write a graph as a list adj, where adj[i] lists the neighbor values of the node with value i + 1, and you receive the node with value 1. The Node class sits at the top of the starter code. Leave it there: the tests build their graphs with it.
adj = [[2, 3], [1, 3], [1, 2, 4], [3]]Output[[2, 3], [1, 3], [1, 2, 4], [3]]Nodes 1, 2 and 3 form a triangle, and node 4 hangs off node 3. The copy has the same edges in the same order, built from four new nodes.
adj = [[]]Output[[]]One node with no neighbors. The copy is one new node with value 1.
node = NoneOutputNoneAn empty graph has nothing to copy.
0 ≤ number of nodes ≤ 3 × 104
Values are 1 to n, each used once.
No node is its own neighbor, and no edge appears twice.
The graph is connected.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.