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


  • 2
    Z

    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>();
            q.add(node);
            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);
                        copycur.neighbors.add(newNode);
                        labels.put(tmp.label, newNode);
                        q.add(tmp);
                    }
                    else{
                        copycur.neighbors.add(labels.get(tmp.label));
                    }
                }
                
            }
            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
    L
    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
    L

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


  • 0
    M

    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
    S

    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.