Clone Graph — Undirected Graph Blind75 LeetCode

https://leetcode.com/problems/clone-graph/?envType=problem-list-v2&envId=oizxjoit

Pattern Recognition: Use a Map to store the node and the clone instead of visiting them, i.e., as we don’t have information about the number of vertices.

Approach: DFS + HashMap for Clones

• We use a hashmap (cloneMap) to keep track of visited nodes.
• Key = original node
• Value = its cloned copy

During DFS:

• If the node has already been cloned (exists in cloneMap), return the clone directly.
• Otherwise, clone the node, store it in the map, and recursively clone all neighbours.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """

        cloneMap = {}

        def dfs(node):

            if not node:
                return None

            if node in cloneMap:
                return cloneMap[node]

            cloneM = Node(node.val)
            cloneMap[node] = cloneM

            for neighbor in node.neighbors:
                cloneM.neighbors.append(dfs(neighbor))
            return cloneM

        return dfs(node)