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)$


Comment