Simple Union Find Solution


  • 0
    S
        public int findCircleNum(int[][] M) {
            int n = M.length;
            if (n == 0)
                return 0;
            int i,j;
            
            int[] ufset = new int[n];
            for (i=0;i<n;i++) {
                ufset[i] = i;
            }
            
            for (i=0;i<n;i++) {
                for (j=0;j<i;j++) {
                    if (M[i][j] == 1) {
                        union(ufset, i, j);
                    }
                }
            }
            int result = 0;
            for (i=0;i<n;i++) {
                if (ufset[i] == i)
                    result++;
            }
            return result;
        }
        
        public int find(int[] ufset, int i) {
            int root = i;
            while (ufset[root] != root) {
                root = ufset[root];
            }
            while (i != root) {
                int temp = ufset[i];
                ufset[i] = root;
                i = temp;
            }
            return root;
        }
        
        public void union (int[] ufset, int i, int j) {
            int rootI = find(ufset, i);
            int rootJ = find(ufset, j);
            
            if (rootI != rootJ) {
                ufset[rootJ] = rootI;
            }
        }
    }

Log in to reply
 

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