mirror of
https://github.com/TheAlgorithms/Python.git
synced 2024-10-05 21:29:29 +00:00
bc8df6de31
* [pre-commit.ci] pre-commit autoupdate updates: - [github.com/astral-sh/ruff-pre-commit: v0.2.2 → v0.3.2](https://github.com/astral-sh/ruff-pre-commit/compare/v0.2.2...v0.3.2) - [github.com/pre-commit/mirrors-mypy: v1.8.0 → v1.9.0](https://github.com/pre-commit/mirrors-mypy/compare/v1.8.0...v1.9.0) * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
79 lines
1.7 KiB
Python
79 lines
1.7 KiB
Python
"""
|
|
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()
|