Back to DSA
Clone Graph
mediumGiven a node in a connected undirected graph, produce a deep copy of the entire graph. Each node holds an integer value and a list of references to its neighbor nodes. The copied graph must have entirely new node objects with the same structure.
Examples
Example 1:
Input:
adjList = [[2,3],[1,4],[1,4],[2,3]]Output:
[[2,3],[1,4],[1,4],[2,3]]Explanation: A 4-node graph is cloned. Node 1 neighbors are 2 and 3; node 2 neighbors are 1 and 4; etc.
Hints
import java.util.*;
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
return dfs(node, map);
}
private Node dfs(Node node, Map<Node, Node> map) {
if (map.containsKey(node)) return map.get(node);
Node clone = new Node(node.val);
map.put(node, clone);
for (Node neighbor : node.neighbors) {
clone.neighbors.add(dfs(neighbor, map));
}
return clone;
}
}Time complexity
O(V + E)Space complexity
O(V)