Can AnyOne help!!! why my Union Find solution will fail in this case


  • 0
    Y
    why my Union Find solution will fail in this case : Input: ["11111","10101","11111"] Output: -1 Expected: 1  
    private static final List<int[]> DIRECTIONS = Arrays.asList(new int[]{1,0}, new int[]{-1,0}, new int[]{0,1}, new int[]{0,-1}); 
    public int numIslands(char[][] grid) {
        
        int row = grid.length;
        if(row == 0) return 0;
        int col = grid[0].length;
        int[] roots = new int[row * col];
        boolean[][] visited= new boolean[row][col];
        int count = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == ‘1’) count++;
                
            }
        }
        if(count == 0) return 0;
        for(int i = 0; i < row * col; i++){
            roots[i] = i;
        }
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == ‘0’ ) continue;
                else{
                   // visited[i][j] =true;
                    for(int[] direction : DIRECTIONS){
                        int x = i + direction[0];
                        int y = j + direction[1];
                        if(x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == ‘0’ || visited[x][y]) continue;
                        if(grid[x][y] == ‘1’){
                        //visited[x][y] = true;
                        int root1 = find(i * col + j,roots);
                        int root2 = find(x * col + y,roots);
                        if(root1 == root2) continue;
                        else{
                            roots[root1] = root2;
                            count —;
                        }
                        }
                       
                    }
                }
            }
        }
        return count ;
        
    }
    public int find(int index, int[] roots ){
        if(roots[index] != index){
            roots[index] = roots[roots[index]];
            index = roots[index];
        }
        return roots[index];
    }

  • 0
    T

    In your find(), it should be a while loop instead of an if block because you may union one root A to another B while there are some children of A. After union to find the root of those children of A your find() can only find A but not B.

    Besides, there is no point to check points to its right or bottom because they're not visited yet.

    Your path compression is also not correct either. However considering your find() method is entirely wrong, I would not blame your path compression.

    Your union operation doesn't check rank either.

    You can check: https://en.wikipedia.org/wiki/Disjoint-set_data_structure. Chinese wikipedia is also pretty good.


  • 0
    Y

    Thank A lot!!! I make a super stupid mistake. I know it need use while rather than if. But, you know, careless!!!


Log in to reply
 

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