Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Each node contains a value and a list of its neighbors.
Example 1
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: Deep copy of the graph.
The graph has at most 100 nodes.0 <= Node.val <= 100DFS with a HashMap<original, clone> to handle cycles.
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> visited = new HashMap<>();
return dfs(node, visited);
}
private Node dfs(Node node, Map<Node, Node> visited) {
if (visited.containsKey(node)) return visited.get(node);
Node clone = new Node(node.val);
visited.put(node, clone); // store before recursing to handle cycles
for (Node neighbor : node.neighbors) {
clone.neighbors.add(dfs(neighbor, visited));
}
return clone;
}Time: O(V+E) · Space: O(V)