[LeetCode] 133. Clone Graph

Posted on | In

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.

Example:

133. Clone Graph

1
2
Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

1
2
3
4
5
Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

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

Explanation

  1. First, we want to create copy of every node first regardless their neighbors. We can achieve this by creating a queue, push the unvisited node inside the queue, and we create a hashmap which connect original node with a new copy of the node. If the map contains the node, then it means this node is visited and we don’t add to the queue.

  2. Next, we want to connect the result node with its neighbors. Since we have a map connect the original node with the same result node. We can easily loop through each original node’s neighbors, and we use the map to get the node and connect its neighbors to the same neighbors as the original node using the hashmap.

Solution

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
38
39
40
41
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        Map<Node, Node> hm = new HashMap<>();

        while (!queue.isEmpty()) {
            Node pNode = queue.poll();
            if (!hm.containsKey(pNode)) {
                Node copy = new Node(pNode.val, new ArrayList<>());
                hm.put(pNode, copy);
                for (Node neighbor: pNode.neighbors) {
                    queue.offer(neighbor);
                }
            }
        }

        for (Node kNode: hm.keySet()) {
            for (Node neighbor: kNode.neighbors) {
                hm.get(kNode).neighbors.add(hm.get(neighbor));
            }
        }

        return hm.get(node);
    }
}