Java union-find with path compression


  • 0
    J
        public boolean validTree(int n, int[][] edges) {
            if (edges.length != n - 1) return false;
            int[] roots = new int[n];
            for (int i = 0; i < n; i++) roots[i] = i;
            
            for (int[] edge : edges) {
                int r1 = find(roots, edge[0]);
                int r2 = find(roots, edge[1]);
                if (r1 == r2) return false;
                roots[r1] = r2;
                roots[edge[1]] = edge[0];
            }
            return true;
        }
        
        private int find(int[] roots, int k) {
            while (roots[k] != k) {
                k = roots[k];
                roots[k] = roots[roots[k]];
            }
            return roots[k];
        }
    

Log in to reply
 

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