Not enough test case


  • 1
    D

    I think No.261 Graph Valid Tree does not have enough test case. I submitted this code:

        if(edges.length == 0 || edges[0].length == 0)   return n == 1;
        HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
        List<List<Integer>> unvisited = new ArrayList<List<Integer>>();
        for(int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            boolean contains0 = visited.containsKey(edge[0]);
            boolean contains1 = visited.containsKey(edge[1]);
            if(contains0 && contains1) {
                if(!visited.get(edge[0]) && !visited.get(edge[1])){
                visited.put(edge[0], true);
                visited.put(edge[1], true);
                }
                else    return false;
            }
            else if(!contains0 && !contains1) {
                visited.put(edge[0], false);
                visited.put(edge[1], false);
                List<Integer> unv = new ArrayList<Integer>();
                unv.add(edge[0]);
                unv.add(edge[1]);
                unvisited.add(unv);
            }
            else {
                visited.put(edge[0], true);
                visited.put(edge[1], true);
            }
        }
        if(visited.keySet().size() != n)    return false;
        if(n == 2)  return true;
        for(int i = 0; i < unvisited.size(); i++) {
            List<Integer> unv = unvisited.get(i);
            if(!visited.get(unv.get(0)) && !visited.get(unv.get(1)))   return false;
        }
        return true;
    

    For case {{0,1},{0,2},{2,5},{3,4}, {3,5}}, this would output false, however, it is still a valid tree.


  • 0
    This post is deleted!

  • 0
    D

    My fault.What I mean is if I use {{0,1},{0,2},{2,5},{3,4}, {3,5}} as the input, my program will output "false", however the input is a valid tree. But my code can still pass all the test cases.


  • 1

    Thanks @derekyyy! You are correct, I have just published your test case. Thanks for making LeetCode OJ better. :)


Log in to reply
 

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