💬 Discord
Sign In
NeetCode #565LC-133MediumGraphsBlind 75NC 150NC 250
← Back to All Problems

#565 · #133 · Clone Graph(克隆图)

📌 Problem Statement & Constraints

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has a value and a list of neighbours. Constraints: 0 <= number of nodes <= 100, 1 <= Node.val <= 100, values are unique.

💡 Core Algorithmic Approaches

  1. DFS with a hash map from original node to its copy.
  2. When a node is revisited, return the existing copy instead of creating a duplicate -- this is what handles cycles.
  3. The map must be populated before recursing into neighbours, otherwise a cycle would recurse forever.
  4. The result is the copy of the starting node.

💻 Benchmark Python3 Implementation

class Solution:
    def cloneGraph(self, node: "Optional[Node]") -> "Optional[Node]":
        if not node:
            return None
        copies = {}

        def dfs(n: "Node") -> "Node":
            if n in copies:
                return copies[n]           # already cloned -> reuse
            copy = Node(n.val)
            copies[n] = copy               # register BEFORE recursing (handles cycles)
            copy.neighbors = [dfs(x) for x in n.neighbors]
            return copy

        return dfs(node)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V) for the map plus O(V) recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Registering the copy after recursing: a cycle would cause infinite recursion.
  • Copying the neighbour list shallowly: the neighbours must be the copies, not the originals.
  • Using the node value as the map key: values are unique here, so it works, but the node identity is the direct key.
  • Forgetting the empty-graph case: node may be None.