It is a classical DFS problem, and my solution applied union-find algorithm that passed all the test cases.

Basic idea is to iterate through every node's neighbours and marked them if they aren't connected.

Finally, if it was the root node then increase the total number of islands.

public class Solution {

```
private int[] sz;
private int[] id;
private int N, M;
public int find(int p) {
while (id[p] != p)
p = id[p];
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (sz[rootP] < sz[rootQ]) {sz[rootQ] += sz[rootP]; id[rootP] = id[rootQ];}
else {sz[rootP] += sz[rootQ]; id[rootQ] = id[rootP];}
}
private boolean inside(int x, int y) {
return (x >= 0 && y >= 0 && x < N && y < M);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length ==0) return 0;
N = grid.length;
M = grid[0].length;
sz = new int[N*M];
id = new int[N*M];
for (int i = 0; i < N*M; i++) {
id[i] = i;
sz[i] = 1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
if (grid[i][j] != '0') {
int tmp = i*M + j;
if (inside(i-1, j) && grid[i-1][j] != '0') union(tmp, tmp - M);
if (inside(i, j-1) && grid[i][j-1] != '0') union(tmp, tmp - 1);
if (inside(i+1, j) && grid[i+1][j] != '0') union(tmp, tmp + M);
if (inside(i, j+1) && grid[i][j+1] != '0') union(tmp, tmp + 1);
}
}
int islands = 0, i = 0;
while (i < N*M) {
if (i == id[i] && grid[i/M][i%M] != '0') islands++;
i++;
}
return islands;
}
```

}