JAVA Union-find solution 16ms O(n^2/2)


  • 0
    T
        class UnionSet{
            int[] arr;
            Set<Integer> set = new HashSet<>();// record the root
            UnionSet(int k) {
                arr = new int[k];
                for (int i = 0; i < k; i ++) {
                    arr[i] = -1;
                    set.add(i);
                }
            }
            public int find (int k) {
                if (arr[k] < 0) {
                    return k;
                }
                if (set.contains(k)) {
                    set.remove(k);
                }
                return arr[k] = find (arr[k]);
            }
            public void union(int i, int j){
                int root1 = find(i);
                int root2 = find(j);
                if (root1 == root2) {
                    return;
                }
                if (-arr[root2] > -arr[root1] ) {
                    arr[root1] = root2;
                    set.remove(root1);
                }else {
                    if (-arr[root1] == -arr[root2]) {
                        arr[root1] --;
                    }
                    arr[root2] = root1;
                    set.remove(root2);
                }
            }
    
            public int getSize(){
                return set.size();
            }
        }
        public int findCircleNum(int[][] M) {
            int N = M.length;
            UnionSet us = new UnionSet(N);
            for (int i = 0; i < N; i ++) {
                for (int j = i + 1 ; j < N; j ++) {
                    if (M[i][j] == 1) {
                        us.union(i, j);
                    }
                }
            }
            return us.getSize();
        }
    

Log in to reply
 

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