WQUPC improved Union Find Java


  • 0
    W

    Based on solution by @jeantimex https://discuss.leetcode.com/topic/21712/ac-java-union-find-solution and https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf.

        public boolean validTree(int n, int[][] edges) {
            if (edges.length != n - 1) return false;
    
            int[] nums = new int[n];
            int[] size = new int[n];
            Arrays.fill(nums, -1);
            Arrays.fill(size, 1);
    
            for (int i = 0; i < edges.length; i++) {
                int x = find(nums, edges[i][0]);
                int y = find(nums, edges[i][1]);
                if (x == y) return false;
                if (size[x] < size[y]) {
                    nums[x] = y;
                    size[y] += size[x];
                } else {
                    nums[y] = x;
                    size[x] += size[y];
                }
            }
            return true;
        }
    
        private int find(int nums[], int i) {
            if (nums[i] == -1) return i;
            while (nums[i] != -1) {
                if (nums[nums[i]] == -1) return nums[i];
                nums[i] = nums[nums[i]];
                i = nums[i];
            }
            return i;
        }
    

Log in to reply
 

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