200. Number of Islands

Union-find O(mn)

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int n = grid.size();
        int m = grid[0].size();
        int dx[] = {0, -1};
        int dy[] = {-1, 0};
        UnionFind uf(n * m);
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                if (grid[row][col] == '0') continue;
                int x = row * m + col;
                uf.add(x);
                for (int i = 0; i < 2; ++i) {
                    if (isValid(grid, row + dy[i], col + dx[i])) {
                        int y = (row + dy[i]) * m + col + dx[i];
                        uf.make_union(x, y);
                    }
                }
            }
        }
        return uf.count;
    }

    bool isValid(vector<vector<char>> &grid, int row, int col) {
        if (row < 0 || col < 0) {
            return false;
        }
        return grid[row][col] == '1';
    }

    struct UnionFind {
        UnionFind(int n) : count(0) {
            parent.resize(n);
        }

        void add(int x) {
            parent[x] = x;
            ++count;
        }

        void make_union(int x, int y) {
            int parent_x = find(x);
            int parent_y = find(y);
            if (parent_x != parent_y) {
                parent[parent_x] = parent_y;
                --count;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return parent[x];
        }

        vector<int> parent;
        int count;
    };
};

DFS O(mn) time

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int n = grid.size(), m = grid[0].size();
        int res = 0;
        int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    dfs(grid, i, j, dy, dx, n, m);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>> &grid, int i, int j, int dy[], int dx[], int n, int m) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0') return;
        grid[i][j] = '0';
        for (int k = 0; k < 4; ++k) {
            dfs(grid, i + dy[k], j + dx[k], dy, dx, n, m);
        }
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        m = grid.size(), n = grid[0].size();
        int res = 0;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == '1') {
                    dfs(grid, r, c);
                    ++res;
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>> &grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r - 1, c);
        dfs(grid, r, c - 1);
    }

    int m, n;
};