133. Clone Graph

Problem Description

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 value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List neighbors;
}

Examples

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.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph has only one node with val = 1 and it has no neighbors.

Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

"""
# 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 []
"""
def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None
    
    # Dictionary to store the cloned nodes
    cloned = {}
    
    def dfs(node: 'Node') -> 'Node':
        if node in cloned:
            return cloned[node]
        
        # Create a new node
        clone = Node(node.val)
        cloned[node] = clone
        
        # Clone all neighbors
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

/*
// Definition for a Node.
class Node {
    public int val;
    public List neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList();
    }
    public Node(int _val, ArrayList _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    private Map cloned = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        if (cloned.containsKey(node)) {
            return cloned.get(node);
        }
        
        // Create a new node
        Node clone = new Node(node.val);
        cloned.put(node, clone);
        
        // Clone all neighbors
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        
        return clone;
    }
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector neighbors;
    Node() {
        val = 0;
        neighbors = vector();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector();
    }
    Node(int _val, vector _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
private:
    unordered_map cloned;
    
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return nullptr;
        }
        
        if (cloned.count(node)) {
            return cloned[node];
        }
        
        // Create a new node
        Node* clone = new Node(node->val);
        cloned[node] = clone;
        
        // Clone all neighbors
        for (Node* neighbor : node->neighbors) {
            clone->neighbors.push_back(cloneGraph(neighbor));
        }
        
        return clone;
    }
};

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */
/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (!node) {
        return null;
    }
    
    const cloned = new Map();
    
    const dfs = (node) => {
        if (cloned.has(node)) {
            return cloned.get(node);
        }
        
        // Create a new node
        const clone = new Node(node.val);
        cloned.set(node, clone);
        
        // Clone all neighbors
        for (const neighbor of node.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        
        return clone;
    };
    
    return dfs(node);
};

/*
// Definition for a Node.
public class Node {
    public int val;
    public IList neighbors;
    
    public Node() {
        val = 0;
        neighbors = new List();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new List();
    }
    
    public Node(int _val, List _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
public class Solution {
    private Dictionary cloned = new Dictionary();
    
    public Node CloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        if (cloned.ContainsKey(node)) {
            return cloned[node];
        }
        
        // Create a new node
        Node clone = new Node(node.val);
        cloned[node] = clone;
        
        // Clone all neighbors
        foreach (Node neighbor in node.neighbors) {
            clone.neighbors.Add(CloneGraph(neighbor));
        }
        
        return clone;
    }
}