岛屿数量并查集

20 Apr 2020 1424字 5分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

200. 岛屿数量

难度中等511收藏分享切换为英文关注反馈

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

示例 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解法

这题应该比较简单，常用的方法有使用 dfs 或 bfs 均可以求解。看了参考解答后，发现可以使用并查集，借此机会学习一下并查集，代码如下：

class UnionFind{
public:
    UnionFind(vector<vector<char>>& grid){
        count = 0;
        int m = grid.size();
        int n = grid[0].size();

        for(int i=0;i<m;++i){
            for(int j=0;j<n;j++){
                if(grid[i][j] == '1'){
                    parent.push_back(i*n + j);
                    count++;
                }else{
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }

    }
    int find(int i){
        if(parent[i] != i){
            parent[i] = find(parent[i]); //压缩路径
        }
        return parent[i];
    }
    void unite(int x, int y){ //合并x子树和y子树
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){
            if(rank[rootx]<rank[rooty]){
                swap(rootx,rooty);
            }
            parent[rooty] = rootx;
            if(rank[rootx] == rank[rooty]) rank[rootx] += 1;
            --count;
        }
    }
    int getCount()const{
        return this->count;
    }
private:
    vector<int> parent;
    vector<int> rank;
    int count;
};
class Solution {
    vector<int> dx = {-1,1,0,0};
    vector<int> dy = {0,0,-1,1};
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m<=0) return 0;
        int n = grid[0].size();

        UnionFind uf(grid);
        for(int x=0;x<m;++x){
            for(int y=0;y<n;++y){
                if(grid[x][y] == '1'){
                    for(int i=0;i<4;i++){
                        int xx = x + dx[i];
                        int yy = y + dy[i];
                        if(xx >= 0 && yy >= 0 && xx < m && yy < n && grid[xx][yy] == '1'){
                            uf.unite(x*n+y, xx*n+yy);
                        }
                    }
                }
            }
        }

        return uf.getCount();
    }
};