Clone Graph

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

"""
Intuition:
The problem is to create a deep copy of a graph where each node may have
multiple neighbors and the graph can contain cycles.

A naive DFS traversal will fail because:
1. The graph may contain cycles, leading to infinite recursion.
2. The same node may be encountered multiple times, causing duplicate copies.

To handle this, we use a hashmap (visited) to store:
    original_node -> cloned_node

Approach:
- Traverse the graph using DFS.
- When visiting a node for the first time:
    * Create its clone.
    * Store it in the hashmap.
- For each neighbor:
    * Recursively clone the neighbor.
    * Attach the cloned neighbor to the current cloned node.
- If a node is already present in the hashmap:
    * Return the already created clone instead of creating a new one.

This ensures:
- Each node is cloned exactly once.
- Cycles are handled safely.
- The structure of the graph is preserved.

In short:
DFS traversal + hashmap (memoization) to avoid duplicate nodes and infinite loops.
"""
def dfs(node,visited):
    if not node:
        return None
    if node in visited.keys():
        return visited[node]

    clone=Node(node.val)
    visited[node]=clone
    for i in node.neighbors:
        clone.neighbors.append(dfs(i,visited))
    return clone


from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited={} #key=original_node and value=cloned_node for the same original node
        return dfs(node,visited)