Union find with weighted tree and path compression


  • 0
    public class Solution {
        public int numIslands(char[][] grid) {
            if(grid.length==0) return 0;
            int m =grid.length;
            int n=grid[0].length;
            int [] arr = new int[m*n];
            Arrays.fill(arr,-1);
            int[] size =new int[m*n];
            Arrays.fill(size,1);
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(grid[i][j]=='0'||arr[i*n+j]!=-1) continue;
                    arr[i*n+j]=i*n+j;
                    if(i>0&&grid[i-1][j]=='1')
                        union(arr,size,i*n+j,(i-1)*n+j);
                    // if(i<m-1&&grid[i+1][j]=='1')
                    //     union(arr,i*n+j,(i+1)*n+j);
                    if(j>0&&grid[i][j-1]=='1')
                        union(arr,size,i*n+j,i*n+(j-1));
                    // if(j<n-1&&grid[i][j+1]=='1')
                    //     union(arr,i*n+j,i*n+(j+1));
                }
            }
            int isLandCount=0;
            for(int i=0 ; i<arr.length;i++)
            {
                if(arr[i]==i)
                 isLandCount++;
            }
            return isLandCount;
        }
        
        public int root(int[] arr, int i)
        {
            while(arr[i]!=i)
            {
                arr[i]=arr[arr[i]];  // path compression
                i=arr[i];
            }
            return i;
        }
        public void union(int[] arr ,int[] size, int i, int j)
        {
            int r1 = root(arr,i);
            int r2 =root(arr,j);
            if(r1==r2)return;
            if(size[r1]<size[r2])    //weighted tree
            {
             arr[r1]=r2;
             size[r2]+=size[r1];
            }
            else{
               arr[r2]=r1;
             size[r1]+=size[r2]; 
            }
        }
    }
    

Log in to reply
 

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