0ms Beat 100% Java, Just use a counter


  • 1
    Q
    1. There should be exactly n-1 edges
    2. Use a counter to track if there are cycles and disconnections
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if(edges.length != n-1){
                return false;
            }
            boolean[] map = new boolean[n];
            Arrays.fill(map, false);
            int cnt = 0;
            for(int i = 0; i < edges.length; ++i){
                int[] tmp = edges[i];
                if(map[tmp[0]] && map[tmp[1]]){  // connect 2 known nodes, subtract 2 to remember it
                    cnt -= 2;
                }
                else if(!map[tmp[0]] && !map[tmp[1]]){  // connect 2 unknown nodes, add 1 to remember it
                    cnt += 1; 
                }
                if(cnt < 0){   // connect 2 known nodes, not enough pairs of unknown nodes. There is cycle
                    return false;
                }
                map[tmp[0]] = true; // mark nodes to known
                map[tmp[1]] = true; // mark nodes to known
            }    
            return cnt == 0 || cnt == 1;  // if cnt > 1, there are disconnections
        }
    }

  • 0
    J

    @qjwzyy It think this doesn't work on test case:

    5
    [[0,1],[4,2],[2,3],[2,4]]


  • 1
    L

    @jade86 It assumes no duplicate edges in the input.


  • 0
    J

    @liyun1988 Hi, thanks for pointing that out. There is a typo to my example, the example that I wanted to mention is

    5
    [0,1] [4,2] [2,3] [3,4]

    This seems to give a count of 1 + 1 - 2 = 0 in the end but it is not a tree.


  • 0
    L

    @jade86 Yep. I just realized that too. I found it fails the case 6
    [[0, 1], [2,3], [4,5], [0,2], [2, 4]], which is similar to yours.


Log in to reply
 

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