为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并，为了避免一些重复的合并，再将这个位置置为0。

最终岛屿的数量就是并查集中连通分量的数目。

class Solution {
public:
    int find(int p[], int x){
        if(p[x] != x)p[x] = find(p, p[x]);
        return p[x];
    }
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int p[n*m];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j ++){
                if(grid[i][j] == '1'){
                    p[i * m + j] = i * m + j;
                }else{
                    p[i * m + j] = -1;
                }
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == '1'){
                    grid[i][j] = '0';
                    if(i - 1 >= 0 && grid[i - 1][j] == '1'){
                        int fa1 = find(p, i * m + j);
                        int fa2 = find(p, (i - 1)*m + j );
                        if(fa1 != fa2){
                            p[fa1] = fa2;
                        }
                    }
                    if(i + 1 < n && grid[i + 1][j] == '1'){
                        int fa1 = find(p, i * m + j);
                        int fa2 = find(p, (i + 1)*m + j );
                        if(fa1 != fa2){
                            p[fa1] = fa2;
                        }
                    }
                    if(j - 1 >= 0 && grid[i][j - 1] == '1'){
                        int fa1 = find(p, i * m + j);
                        int fa2 = find(p, i*m + j - 1);
                        if(fa1 != fa2){
                            p[fa1] = fa2;
                        }
                    }
                    if(j + 1 < m && grid[i][j + 1] == '1'){
                        int fa1 = find(p, i * m + j);
                        int fa2 = find(p, i*m + j + 1);
                        if(fa1 != fa2){
                            p[fa1] = fa2;
                        }
                    }
                }
            }
        }
        int cnt = 0;
        for(int i = 0; i < m * n;i++){
            if(p[i] == i){
                cnt ++;
            }
        }
        return cnt;
    }
};

时间复杂度：O(MN×α(MN))，其中 M 和 N 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作(unite)的时间复杂度为 α(MN)，其中 α(x) 为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 α(x) 的值不会超过 5，因此也可以看成是常数时间复杂度。

空间复杂度：O(MN)，这是并查集需要使用的空间。