You are handed one node of a connected, undirected graph. Every node holds a whole-number val and a list neighbors of the nodes it is joined to.
Build a deep copy of the whole graph and return the copy of the node you were given. A deep copy is made of brand-new nodes only: each new node has its original's value, and its neighbours are the new nodes standing in for its original's neighbours. Not one node of the copy may be a node of the original graph, and the answer is rejected as "not a copy" if it reaches any of them.
How graphs are written here. With n nodes, the nodes have the values 1 to n, and the graph is written as a list of n lists: list i holds the values of node i's neighbours, in the order that node lists them. You are given the node with value 1. [] is a graph with no nodes at all, so you are given nothing (None/null/nil) and return nothing.
Your answer is written back the same way, so give each copy its neighbours in the same order as its original.
Example 1
Input: node = [[2,3],[1,3,4],[1,2],[2,5],[4]]
Output: [[2,3],[1,3,4],[1,2],[2,5],[4]]
Starting from node 1 you can reach all five nodes, so all five are copied. Node 2's copy has three neighbours, the copies of 1, 3 and 4, in that order. The triangle 1 – 2 – 3 means you meet some nodes more than once; each must still be copied exactly once.
Example 2
Input: node = [[4,2],[1,3],[2,4],[3,1]]
Output: [[4,2],[1,3],[2,4],[3,1]]
A ring of four nodes. Node 1 lists 4 before 2, and its copy does the same.
Example 3
Input: node = [[2],[1]]
Output: [[2],[1]]
Two nodes joined to each other.
Constraints
0 and 100 nodes.1 to n, one node each, and you are given node 1.a lists b exactly when b lists a.1.Walk the graph from the node you're given and keep a map from each original node to its copy. The map is what stops a cycle from being copied again and again.
Copying one node is easy: make a new node with the same val. The hard part is its neighbors list, which has to hold copies of its neighbours, and those neighbours have neighbours of their own.
Time O(V + E)Space O(V)
The full walkthrough and code are part of Premium
[[2,3],[1,3,4],[1,2],[2,5],[4]]
[[2,3],[1,3,4],[1,2],[2,5],[4]]