Help! Please find where is my bug? Java union find


  • 0
    S
    public int numIslands(char[][] grid) {
            int m = grid.length;
            if (m == 0) return 0;
            int n = grid[0].length;
            Union u = new Union(m*n);
            for (int i = 0; i < m; i++){
                for (int j = 0; j < n; j++){
                    if (grid[i][j] == '0') {
                        continue;
                    }
                    int index = i*n + j;
                    u.add(index);
                    if (i > 0 && grid[i-1][j] == '1'){
                        u.union(index, index - n);
                    }
                    if (j > 0 && grid[i][j-1] == '1'){
                        u.union(index, index - 1);
                    }
                }
            }
            return u.getCount();
    }
    class Union{
            private int count;
            private int[] root;
            public Union(int n){
                count = 0;
                root = new int[n];
                Arrays.fill(root, -1);
            }
            public void add(int i){
                root[i] = i;
                count++;
            }
            public void union(int n1, int n2){
                int root1 = find(n1);
                int root2 = find(n2);
                if (root1 != root2){
                    root[n1] = n2;
                    count--;
                }
            }
            private int find(int index){
                int i = index;
                while (root[i] != i){
                    i = root[i];
                }
                root[index] = i;
                return i;
            }
            public int getCount(){
                return count;
            }
            
        }

Log in to reply
 

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