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];
}
Can AnyOne help!!! why my Union Find solution will fail in this case


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/Disjointset_data_structure. Chinese wikipedia is also pretty good.