Java solution using Union Find


  • 3
    L
    public class Solution {
    public int numIslands(char[][] grid) {
        if(grid.length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    count++;
                }
            }
        }
        UnionFind uf = new UnionFind(m,n,count);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    if(j+1 < n && grid[i][j+1] == '1') uf.union(i*n+j,i*n+j+1);
                    if(i+1 < m && grid[i+1][j] == '1') uf.union(i*n+j,(i+1)*n+j);
                }
            }
        }
        return uf.count;
    }
    private class UnionFind{
        int[] id;
        int[] rank;
        int count;
        UnionFind(int m,int n,int count){
            id = new int[m*n];
            rank = new int[m*n];
            this.count = count;
            for(int i = 0; i < m*n; i++){
                id[i] = i;
                rank[i] = 1;
            }
        }
        int find(int i){
            if(i != id[i]){
                id[i] = find(id[i]);
            }
            return id[i];
        }
        void union(int i,int j){
            int ii = find(i);
            int jj = find(j);
            if(ii == jj) return;
            if(rank[ii] > rank[jj]){
                id[jj] = ii;
                rank[ii] += rank[jj];
            }
            else{
                id[ii] = jj;
                rank[jj] += rank[ii];
            }
            count--;
            return;
        }
    }
    

    }


  • 0
    X

    Why do we have to update the rank? In the function UnionFind.union(int, int),
    you wrote
    if(rank[ii] > rank[jj]){
    id[jj] = ii;
    rank[ii] += rank[jj];
    }
    can we just do
    if(ii>jj){
    id[jj] = ii;
    }
    (and the same for the else part)?


  • 0
    L

    rank is used to optimization.rank[ii] records total nodes that tree takes ii as root .Your thought also is right ,but you can further think,if we union without compare rank,we maybe hang large tree on small tree ,it maybe increse height of unioned tree and is bad for us in find operation.so we need compare rank and hang small tree on large tree.You can refer to this blog to understand Union Find algorithm.http://blog.csdn.net/dm_vincent/article/details/7655764


  • 0
    X

    Thanks!!
    So rank[] records the size the branch, and we want to merge smaller components into larger ones, not vice versa. I think I got it. Thanks!


  • 0
    W
    This post is deleted!

Log in to reply
 

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