# [200\. Number of Islands](https://leetcode.com/problems/number-of-islands/)

:::spoiler Solution - DFS

class Solution {
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int island = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    dfs(grid, i, j);
                    island++;
                }
            }
        }
        return island;
    }
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0') return;
        
        grid[i][j] = '0';
        vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        for (const auto& dir : directions)
        {
            dfs(grid, i + dir[0], j + dir[1]);
        }
    }
};

- T: $O(M \cdot N)$
- S: $O(M \cdot N)$
:::

:::spoiler Solution - BFS

class Solution {
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        int island = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')
                {
                    grid[i][j] = '0';
                    
                    queue<pair<int, int>> q;

                    q.push({i, j});

                    vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
                    while (!q.empty())
                    {
                        auto node = q.front(); q.pop();
                        for (const auto& dir : directions)
                        {
                            int new_i = node.first + dir[0];
                            int new_j = node.second + dir[1];
                            if (new_i < 0 || new_j < 0 || new_i >= m || new_j >= n || grid[new_i][new_j] == '0') continue;
                            grid[new_i][new_j] = '0';
                            q.push({new_i, new_j});
                        }
                    }
                    island++;
                }
            }
        }
        return island;
    }
};

- T: $O(M \cdot N)$
- S: $O(\min(M \cdot N))$
:::

:::spoiler Solution - Union Find

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;    
public:
    UnionFind(vector<vector<char>>& grid) {
        count = 0;
        int rows = grid.size(), cols = grid[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    parent.push_back(i * cols + j);
                    // 將每一個格子當成 root
                    ++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 Union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) 
                parent[rooty] = rootx;
            else if (rank[rootx] < rank[rooty]) 
                parent[rootx] = rooty;
            else {
                parent[rooty] = rootx; 
                rank[rootx] += 1;
            }
            --count;
        }
    }

    int getCount() const {
        return count;
    }
};

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

        vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        UnionFind uf (grid);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    // 標記為 0，代表走訪過了
                    grid[i][j] = '0';
                    for(auto& dir : directions) {
                        int new_i = i + dir[0];
                        int new_j = j + dir[1];
                        if(new_i < 0 || new_j < 0 || new_i >= rows || new_j >= cols || grid[new_i][new_j] == '0')
                            continue;
                        uf.Union(i * cols + j, new_i * cols + new_j);
                    }
                }
            }
        }
        return uf.getCount();        
    }
};

- T: $O(M \cdot N)$
- S: $O(M \cdot N)$
:::