deep_clone_graph.py

"""
LeetCode 133. Clone Graph
https://leetcode.com/problems/clone-graph/

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

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

fromdataclassesimportdataclass


@dataclass
classNode:
value: int=0
neighbors: list["Node"] |None=None

def__post_init__(self) ->None:
"""
 >>> Node(3).neighbors
 []
 """
self.neighbors=self.neighborsor []

def__hash__(self) ->int:
"""
 >>> hash(Node(3)) != 0
 True
 """
returnid(self)


defclone_graph(node: Node|None) ->Node|None:
"""
 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
 """
ifnotnode:
returnNone

originals_to_clones= {} # map nodes to clones

stack= [node]

whilestack:
original=stack.pop()

iforiginalinoriginals_to_clones:
continue

originals_to_clones[original] =Node(original.value)

stack.extend(original.neighborsor [])

fororiginal, cloneinoriginals_to_clones.items():
forneighborinoriginal.neighborsor []:
cloned_neighbor=originals_to_clones[neighbor]

ifnotclone.neighbors:
clone.neighbors= []

clone.neighbors.append(cloned_neighbor)

returnoriginals_to_clones[node]


if__name__=="__main__":
importdoctest

doctest.testmod()