Concise and Clear UnionFind Solution


  • 0
    class UF {
        int[] ids;
        int[] sizes;
        public UF(int n) {
            ids = new int[n];
            sizes = new int[n];
            for (int i = 0; i < n; i++) {
                ids[i] = i;
                sizes[i] = 1;
                }
        }
        public void union(int a, int b) {
            int i = find(a);
            int j = find(b);
            if (i != j) {
                if(sizes[i] > sizes[j]) {
                    ids[j] = i;
                    sizes[i] += sizes[j];
                }
                else {
                    ids[i] = j;
                    sizes[j] += sizes[i];
                }
            }
        } 
        public int find(int i) {
            while (i != ids[i]) {
                ids[i] = ids[ids[i]];
                i = ids[i];
            }
            return i;
        }
    }
    public class Solution {
        public int findCircleNum(int[][] M) {
            if (M == null || M.length == 0 || M[0].length == 0) return 0;
            int n = M.length ;  
            UF uf = new UF(n);
            int res = n;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (M[i][j] == 1) {
                        if (uf.find(i) != uf.find(j)) {
                            uf.union(i, j);
                            res--;
                        }
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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