Practice/Meta/Design a Graph Storage and Cloning System

Design a Graph Storage and Cloning System

CodingMust

Problem

Design and implement a deep copy mechanism for an undirected graph data structure. You are given a reference to a node in a connected undirected graph where each node contains an integer value and a list of its neighbors.

Your task is to create a completely independent copy of the entire graph, ensuring that:

• All nodes are duplicated with the same values
• All edge relationships are preserved in the new graph
• The cloned graph shares no references with the original graph (true deep copy)
• Modifications to the cloned graph do not affect the original, and vice versa

The graph is represented using an adjacency list where each node contains:

• val: an integer value for the node
• neighbors: a list of references to neighboring nodes

Requirements

1. Implement a Node class with value and neighbors properties
2. Create a cloneGraph function that takes a node reference and returns the corresponding node in the cloned graph
3. Handle graphs with cycles without infinite loops
4. Maintain all bidirectional relationships between nodes
5. Return null/None if the input is null/None
6. Ensure true deep copy - no shared references between original and clone

Constraints

• Number of nodes in the graph: 0 ≤ n ≤ 100
• Node values: 1 ≤ Node.val ≤ 100
• Node values are unique (each node can be identified by its value)
• No self-loops or duplicate edges
• The graph is undirected (if node A is in B's neighbor list, B is in A's neighbor list)
• Time complexity target: O(n + e) where n is nodes and e is edges
• Space complexity target: O(n) for the cloned graph plus recursion/iteration overhead

Examples

Example 1:

Input: Node with val=1, no neighbors Output: New Node with val=1, no neighbors Explanation: Single isolated node is cloned with same value and empty neighbor list

Example 2:

Input: Graph [[2,4],[1,3],[2,4],[1,3]] Node 1 connects to nodes 2 and 4 Node 2 connects to nodes 1 and 3 Node 3 connects to nodes 2 and 4 Node 4 connects to nodes 1 and 3 Output: Deep copy with identical structure Explanation: All four nodes and their connections are duplicated in new graph

Example 3:

Input: null Output: null Explanation: Empty graph returns null

Example 4:

Input: Graph forming triangle [[2,3],[1,3],[1,2]] Node 1 connects to nodes 2 and 3 Node 2 connects to nodes 1 and 3 Node 3 connects to nodes 1 and 2 Output: Deep copy maintaining triangle structure Explanation: Cycle is properly handled without infinite recursion