Node(val, neighbors=None) is in the starter. Keep it. neighbors is a list of Nodes.
Implement clone_graph(node) -> Node | None.
node is one node of a connected, undirected graph (or None for an empty graph). Every node has a distinct val. An edge between a and b appears in both a.neighbors and b.neighbors. There are no self-loops or repeated edges.
Return the matching node of a deep copy: a new Node for every original node, with the same val, and neighbour lists that point to the copies, in the same order as the original. The copy must not share any Node object with the original.
a, b, c = Node(1), Node(2), Node(3)
a.neighbors = [b, c]; b.neighbors = [a, c]; c.neighbors = [a, b] # a triangle
copy = clone_graph(a)
copy is not a # True
[n.val for n in copy.neighbors] # [2, 3]
copy.neighbors[0].neighbors[0] is copy # True: the copied edge leads back to the copy
Graphs have up to 5,000 nodes, may contain cycles, and may be one long path, so each node must be copied exactly once and deep recursion will hit Python's limit (about 1,000 frames).
Show hint
When you reach a node for the second time, you need its copy, not a new one. Remember which copy belongs to which original.