iframe-proxy | Sunbelt Computer Software

History

78 lines (55 loc) · 1.7 KB

Raw

"""

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.

"""

from dataclasses import dataclass

@dataclass

class Node:

value: int = 0

neighbors: list["Node"] | None = None

def __post_init__(self) -> None:

"""

>>> Node(3).neighbors

[]

"""

self.neighbors = self.neighbors or []

def __hash__(self) -> int:

"""

>>> hash(Node(3)) != 0

True

"""

return id(self)

def clone_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

"""

if not node:

return None

originals_to_clones = {} # map nodes 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()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

deep_clone_graph.py

Latest commit

History

deep_clone_graph.py

File metadata and controls