Reference: LeetCode
Difficulty: Medium

Problem

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 (List[Node]) of its neighbors.

Note:

  • The number of nodes will be between 1 and 100.
  • The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
  • Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
  • You must return the copy of the given node as a reference to the cloned graph.

Analysis

DFS (recursion)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public Node cloneGraph(Node node) {
  Map<Node, Node> map = new HashMap<>(); // <oldNode, newNode>
  dfs(node, map);
  return map.get(node);
}

private void dfs(Node node, Map<Node, Node> map) {
  dfsSetMap(node, new HashSet<>(), map);
  dfsSetNeighbors(node, new HashSet<>(), map);
}

private void dfsSetMap(Node node, Set<Node> marked, Map<Node, Node> map) {
  // visit
  marked.add(node);
  Node newNode = new Node(node.val, null); // copy
  map.put(node, newNode);
  // neighbors
  for (Node n : node.neighbors) {
    if (!marked.contains(n)) {
      dfsSetMap(n, marked, map);
    }
  }
}

private void dfsSetNeighbors(Node node, Set<Node> marked, Map<Node, Node> map) {
  // visit
  marked.add(node);
  List<Node> newList = new ArrayList<>();
  for (Node n : node.neighbors) newList.add(map.get(n));
  map.get(node).neighbors = newList;
  // neighbors
  for (Node n : node.neighbors) {
    if (!marked.contains(n)) {
      dfsSetNeighbors(n, marked, map);
    }
  }
}

Optimization: We can combine dfsSetMap and dfsSetNeighbors to get clean code!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void dfs(Node node, Map<Node, Node> map) {
  dfsCopy(node, new HashSet<>(), map);
}

private void dfsCopy(Node node, Set<Node> marked, Map<Node, Node> map) {
  // visit
  marked.add(node);
  Node newNode = new Node(node.val, null); // copy
  map.put(node, newNode);
  // visit neighbors
  for (Node n : node.neighbors) {
    if (!marked.contains(n)) {
      dfsCopy(n, marked, map);
    }
  }
  // set neighbors
  List<Node> newList = new ArrayList<>();
  for (Node n : node.neighbors) newList.add(map.get(n));
  map.get(node).neighbors = newList;
}

Time: $O(V + E)$
Space: $O(V)$