Clone Graph

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node: Node | None) -> Node | None:
    if not node:
        return None
    cloned = {}

    def dfs(n: Node) -> Node:
        if n in cloned:
            return cloned[n]
        copy = Node(n.val)
        cloned[n] = copy
        copy.neighbors = [dfs(nb) for nb in n.neighbors]
        return copy

    return dfs(node)

if __name__ == '__main__':
    # Build graph: 1 -- 2 -- 3 -- 4 -- 1
    n1, n2, n3, n4 = Node(1), Node(2), Node(3), Node(4)
    n1.neighbors = [n2, n4]
    n2.neighbors = [n1, n3]
    n3.neighbors = [n2, n4]
    n4.neighbors = [n3, n1]

    clone = clone_graph(n1)
    print(clone.val)                                  # 1
    print([n.val for n in clone.neighbors])           # [2, 4]
    print(clone is not n1)                            # True
    print(clone.neighbors[0] is not n2)               # True