Union find sol(Java)


  • 0
    R
    public class Solution {
        public int findCircleNum(int[][] M) {
            int n = M.length;
            int[] parent = new int[n], rank = new int[n];
            
            for(int i = 0; i < n; ++i) {
                parent[i] = i;
                rank[i] = 1;
            }
            
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(i != j && M[i][j] == 1) union(parent, rank, i, j);
                }
            }
            
            Set<Integer> set = new HashSet<>();
            for(int i = 0; i < n; ++i) {
                set.add(find(parent, i));
            }
            
            return set.size();
        }
        
        private void union(int[] parent, int[] rank, int x, int y) {
            int pX = find(parent, x), pY = find(parent, y);
            
            if(pX == pY) return;
            
            int rankX = rank[pX], rankY = rank[pY];
            
            if(rankX >= rankY) {
                if(rankX == rankY) rank[pX]++;
                parent[pY] = pX;
            } else {
                parent[pX] = pY;
            }
        }
        
        private int find(int[] parent, int x) {
            if(parent[x] == x) return x;
            int id = find(parent, parent[x]);
            parent[x] = id;
            return id;
        }
    }
    
    
    

Log in to reply
 

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