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

  • 2

    I have the following code got Accepted:

    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node == null) return null;
            LinkedList<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
            UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
            HashMap<Integer, UndirectedGraphNode> labels = new HashMap<Integer, UndirectedGraphNode>();
            labels.put(copy.label, copy);
                UndirectedGraphNode cur = q.poll();
                UndirectedGraphNode copycur = labels.get(cur.label);
                Iterator<UndirectedGraphNode> iter = cur.neighbors.iterator();
                    UndirectedGraphNode tmp = iter.next();
                        UndirectedGraphNode newNode = new UndirectedGraphNode(tmp.label);
                        labels.put(tmp.label, newNode);
            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?

  • 3
    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.

  • 0

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

  • 0

    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>();

  • 0

  • 0

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

Log in to reply

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