leetcode 133 clone graph https leetcode comproblemsclonegraph 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 listnode of its neighbors node3 neighbors hashnode3 0 true this function returns a clone of a connected undirected graph clonegraphnode1 nodevalue1 neighbors clonegraphnode1 node2 nodevalue1 neighborsnodevalue2 neighbors clonegraphnone is none true node 3 neighbors hash node 3 0 true 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 map nodes to clones
from dataclasses import dataclass


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

    def __post_init__(self) -> None:
        
        self.neighbors = self.neighbors or []

    def __hash__(self) -> int:
        
        return id(self)


def clone_graph(node: Node | None) -> Node | None:
    
    if not node:
        return None

    originals_to_clones = {}  

    stack = [node]

    while stack:
        original = stack.pop()

        if original in originals_to_clones:
            continue

        originals_to_clones[original] = Node(original.value)

        stack.extend(original.neighbors or [])

    for original, clone in originals_to_clones.items():
        for neighbor in original.neighbors or []:
            cloned_neighbor = originals_to_clones[neighbor]

            if not clone.neighbors:
                clone.neighbors = []

            clone.neighbors.append(cloned_neighbor)

    return originals_to_clones[node]


if __name__ == "__main__":
    import doctest

    doctest.testmod()