# What does test case {0, 0, 0} mean?

• I have the following code got Accepted:

``````public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
HashMap<Integer, UndirectedGraphNode> labels = new HashMap<Integer, UndirectedGraphNode>();
labels.put(copy.label, copy);
while(!q.isEmpty()){
UndirectedGraphNode cur = q.poll();
UndirectedGraphNode copycur = labels.get(cur.label);
Iterator<UndirectedGraphNode> iter = cur.neighbors.iterator();
while(iter.hasNext()){
UndirectedGraphNode tmp = iter.next();
if(!labels.containsKey(tmp.label)){
UndirectedGraphNode newNode = new UndirectedGraphNode(tmp.label);
labels.put(tmp.label, newNode);
}
else{
}
}

}
return copy;
}
}
``````

The idea is to implement a BFS while keeping track of the nodes I added to the new graph. If I have already added a node to the graph, I just do not push it into the queue, so that avoids the potential infinite loop when the graph has a loop in it.

The code is passed, but I had one test case that I have no idea how I solved it. For test case {0, 0, 0}, I simply assumed that it means for a node with label 0, it has two self-cycles. Is that what it means?

In addition, I feel that my code can be more efficient. Is the HashMap called "labels" necessary? Is LinkedList the best choice to implement a queue in Java?

1. Indeed, {0,0,0} is the graph with only one node and two self-cycles.
Your algorithm does exactly what is needed in this case. Before the
while loop, you copied 0 and put a link to the copy of 0 in the map.
The, you iterate over the neighbors of 0. These neighbors (0,0) are
already in the map, so you simply add the self-cycles to the copy.
2. The map is necessary here.
3. LinkedList is not the best choice to implement a queue in Java. Look at the doc of the queue interface to see what are the classes that implement it. In particular, have a look at ArrayDeque. It is also a good practice to declare your queue by: Queue<UndirectedGraphNode> q = new ArrayDeque<UndirectedGraphNode>; this way if you change the implementation of the queue, you need to change your code at only one place.

• In a graph there can be only one edge between two vertices. The {0, 0, 0} test case is invalid.

• Agree - the map is necessary, but it should map between node objects directly for being flexible, i.e. HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

• Can anyone explain to me why Hashmap is necessary? Wondering if a Hashset is sufficient?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.