This function returns a clone of a connected undirected graph. >>> clone_graph(Node(1)) Node(value=1, neighbors=[]) >>> clone_graph(Node(1, [Node(2)])) Node(value=1, neighbors=[Node(value=2, neighbors=[])]) >>> clone_graph(None) is None True
(node: Node | None)
| 34 | |
| 35 | |
| 36 | def clone_graph(node: Node | None) -> Node | None: |
| 37 | """ |
| 38 | This function returns a clone of a connected undirected graph. |
| 39 | >>> clone_graph(Node(1)) |
| 40 | Node(value=1, neighbors=[]) |
| 41 | >>> clone_graph(Node(1, [Node(2)])) |
| 42 | Node(value=1, neighbors=[Node(value=2, neighbors=[])]) |
| 43 | >>> clone_graph(None) is None |
| 44 | True |
| 45 | """ |
| 46 | if not node: |
| 47 | return None |
| 48 | |
| 49 | originals_to_clones = {} # map nodes to clones |
| 50 | |
| 51 | stack = [node] |
| 52 | |
| 53 | while stack: |
| 54 | original = stack.pop() |
| 55 | |
| 56 | if original in originals_to_clones: |
| 57 | continue |
| 58 | |
| 59 | originals_to_clones[original] = Node(original.value) |
| 60 | |
| 61 | stack.extend(original.neighbors or []) |
| 62 | |
| 63 | for original, clone in originals_to_clones.items(): |
| 64 | for neighbor in original.neighbors or []: |
| 65 | cloned_neighbor = originals_to_clones[neighbor] |
| 66 | |
| 67 | if not clone.neighbors: |
| 68 | clone.neighbors = [] |
| 69 | |
| 70 | clone.neighbors.append(cloned_neighbor) |
| 71 | |
| 72 | return originals_to_clones[node] |
| 73 | |
| 74 | |
| 75 | if __name__ == "__main__": |