Clone Graph medium

Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list of its neighbors (Node[]).

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. Node 1's neighbors are node 2 and 4. Node 2's neighbors are node 1 and 3. Node 3's neighbors are node 2 and 4. Node 4's neighbors are node 1 and 3.

Example 2

Input: adjList = [[]] Output: [[]] Explanation: Node 0 doesn't have any neighbors.

Steps

1. Handle Base Case: If the input node is null, return null.
2. Create a HashMap: Use a hashmap (dictionary in C#) to store the mapping between original nodes and their cloned counterparts. This prevents infinite loops and ensures we don't create duplicate nodes.
3. Depth-First Search (DFS): Perform a depth-first search (DFS) starting from the input node.
4. Clone Node: For each node encountered during DFS:
   • If the node is already in the HashMap (meaning it's already cloned), retrieve its clone.
   • Otherwise, create a new node with the same val and add it to the HashMap.
5. Clone Neighbors: For each neighbor of the current node:
   • Recursively call the cloning function on the neighbor to get its cloned version.
   • Add the cloned neighbor to the neighbors list of the cloned current node.
6. Return the Cloned Node: After the DFS completes, the cloned root node will be available in the HashMap. Return this cloned node.

Explanation

The core idea is to avoid creating duplicate nodes and to ensure that every node's connections are correctly replicated. The HashMap acts as a memory to track nodes that have already been cloned. The DFS ensures that we visit all nodes and their neighbors systematically.

Code

using System;
using System.Collections.Generic;

public class Node {
    public int val;
    public IList<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new List<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new List<Node>();
    }
    public Node(int _val, IList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    private Dictionary<Node, Node> visited = new Dictionary<Node, Node>();

    public Node CloneGraph(Node node) {
        if (node == null) return null;

        if (visited.ContainsKey(node)) {
            return visited[node];
        }

        Node cloneNode = new Node(node.val);
        visited[node] = cloneNode;

        foreach (Node neighbor in node.neighbors) {
            cloneNode.neighbors.Add(CloneGraph(neighbor));
        }

        return cloneNode;
    }
}

Complexity

• Time Complexity: O(N + M), where N is the number of nodes and M is the number of edges. This is because we visit each node and edge once during the DFS.
• Space Complexity: O(N), where N is the number of nodes. The space is mainly used by the HashMap to store the cloned nodes and the call stack during the recursive DFS. In the worst-case scenario (a completely connected graph), the call stack could reach a depth of N.