Union find easy to understand java


  • 0
    O
    public class Solution {
        public int findCircleNum(int[][] matrix) {
            int n = matrix.length;
            if(n <= 1){
                return n;
            }
            int[] roots = new int[n];
            for(int i = 0; i < n; i++){
                roots[i] = i;
            }
            int count = n;
            for(int i = 0; i < n; i++){
                for(int j = i + 1; j < n; j++){
                    if(matrix[i][j] == 0){
                        continue;
                    }
                    int root1 = helper(roots, i);
                    int root2 = helper(roots, j);
                    if(root1 != root2){
                        roots[root2] = root1;
                        count--;
                    }
                }
            }
            return count;
        }
        public int helper(int[] roots, int i){
            if(roots[i] != i){
                roots[i] = helper(roots, roots[roots[i]]);
            }
            return roots[i];
        }
    }
    

Log in to reply
 

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