leetcode-200 | LDK's Blog

leetcode-200 岛屿数量

标签：

DFS
BFS
UnionFind

思路：

三种思路：

使用DFS，从某个1开始搜索，标记所有搜索过的1为2（或者其他非1数值），直到找不到相邻的1，至此记为一个岛屿。循环遍历全图，即可得到岛屿数量。
使用BFS，原理同上
使用并查集。

题解代码：

并查集版本

class UnionFind {
public:
    UnionFind(std::vector<std::vector<char>>& grid) {
        this->count = 0;
        int line = grid.size();
        int column = grid[0].size();
        for (int i = 0; i < line; ++i) {
            for (int j = 0; j < column; ++j) {
                if (grid[i][j] == '1') {
                    this->parent.push_back(i * column + j); // 祖宗等于自身
                    ++this->count;
                } else {
                    this->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) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) // 属于不同集，准备合并
        {
            if (rank[rootx] < rank[rooty]) // 确保 x 高度 >= y
            {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx; // 将 y 挂在 x 下面
            if (rank[rootx] == rank[rooty]) {
                rank[rootx] += 1; // 如果合并前高度相等，合并后 x 高度 +1
            }
            --count;
        }
    }

    int getCount() const { return this->count; }

    int count;
    std::vector<int> rank;
    std::vector<int> parent;
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int line = grid.size();
        if (!line) {
            return 0;
        }
        int column = grid[0].size();

        UnionFind ufind(grid);
        int num_islands = 0;
        for (int i = 0; i < line; ++i) {
            for (int j = 0; j < column; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                        ufind.unite(i * column + j, (i - 1) * column + j);
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                        ufind.unite(i * column + j, i * column + j - 1);
                    }
                    if (i + 1 < line && grid[i + 1][j] == '1') {
                        ufind.unite(i * column + j, (i + 1) * column + j);
                    }
                    if (j + 1 < column && grid[i][j + 1] == '1') {
                        ufind.unite(i * column + j, i * column + j + 1);
                    }
                }
            }
        }
        return ufind.getCount();
    }
};