Problem #133: Clone Graph

Intuition & Strategy Breakdown

Use BFS/DFS with a hash map mapping original nodes to cloned nodes to handle graph cycles and clone all nodes and edges.

Python Solution

\nclass Solution:\n    def cloneGraph(self, node: 'Node') -> 'Node':\n        if not node:\n            return None\n        old_to_new = {node: Node(node.val)}\n        q = collections.deque([node])\n        while q:\n            curr = q.popleft()\n            for nbr in curr.neighbors:\n                if nbr not in old_to_new:\n                    old_to_new[nbr] = Node(nbr.val)\n                    q.append(nbr)\n                old_to_new[curr].neighbors.append(old_to_new[nbr])\n        return old_to_new[node]\n

Java Solution

\nclass Solution {\n    public Node cloneGraph(Node node) {\n        if (node == null) return null;\n        Map oldToNew = new HashMap<>();\n        Queue queue = new LinkedList<>();\n        oldToNew.put(node, new Node(node.val));\n        queue.add(node);\n        while (!queue.isEmpty()) {\n            Node curr = queue.poll();\n            for (Node neighbor : curr.neighbors) {\n                if (!oldToNew.containsKey(neighbor)) {\n                    oldToNew.put(neighbor, new Node(neighbor.val));\n                    queue.add(neighbor);\n                }\n                oldToNew.get(curr).neighbors.add(oldToNew.get(neighbor));\n            }\n        }\n        return oldToNew.get(node);\n    }\n}\n