```
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;
}
}
```

}