1ms java Union Find solution


  • 0
    Q
    public boolean validTree(int n, int[][] edges){
            int[] heads = new int[n];
            for(int i = 0; i< n; i++) heads[i] = i;
            
            for(int[] e : edges){
                int h1 = find(heads, e[0]);
                int h2 = find(heads, e[1]);
                
                if(h1 == h2) return false;
                heads[h1] = h2;
                n--;
            }
            return n == 1;
        }
        
        int find(int[] heads, int h){
            while(heads[h] != h){
                // path compression
                heads[h] = heads[heads[h]];
                h = heads[h];
            }
            
            return h;
        }
    

Log in to reply
 

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