Union find or DFS/BFS

Union find and DFS/BFS have some common part. Union find can group the same group elements into one group and give them a group ID. BFS/DFS can traverse all the elements within the group.

Here we have a problem can be solved by

• using union find + DFS/BFS
• Using purely DFS

1905. Count Sub Islands

using union find + DFS/BFS

Intuition:

Based on the problem description, we can use Union Find to give the cells of each island in grid1 a group ID. Then for the island in grid2, we just check whether all the cells in the island of grid2 has the same group id based on the id created from grid1.

This is purely simulate the problem. Reference code can be found here

vector<pair<int, int>> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
class UF{
    public:
    vector<int> roots;
    
    UF(int N){
        roots.assign(N, 0);
        for (int i = 0; i < N; ++i) roots[i] = i;
    }
    int findSet(int i) {
        return roots[i] == i ? i : roots[i] = findSet(roots[i]);
    }
    void unionSet(int i, int j) {
        int x = findSet(i), y =findSet(j);
        if (x == y) return;
        roots[x] = y;
    }
};
class Solution {
public:
    int n , m;
    vector<vector<int>> grid;
    void dfs(int i, int j, vector<vector<int>>& grid1, UF& uf) {
        grid1[i][j] = 0;
        int r = 0, c = 0;
        for (auto [di, dj] : dirs){
            r = i + di, c = j + dj;
            if (r < 0 || r >= n || c < 0 || c >= m || grid1[r][c] == 0) continue;
            grid1[r][c] = 0;
            uf.unionSet(i*m + j, r*m + c);
            dfs(r, c, grid1, uf);
        }
        return;
    }
     bool dfs2(int i, int j,  vector<vector<int>>& grid2,UF& uf,int root){
        grid2[i][j] = 0;
        bool good = true;
        int r = 0, c = 0;
        for (auto [di, dj] : dirs){
            r = i + di, c = j + dj;
            if (r < 0 || r >= n || c < 0 || c >= m || grid2[r][c] == 0) continue;
            grid2[r][c] = 0;
            auto newroot = uf.findSet(r*m + c);
            if (newroot != root) good = false;
            bool thisgood = dfs2(r, c, grid2, uf, root);
            if (!thisgood) good = false;
        }
         return good;
     }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        this->grid = grid1;
        const int n = grid1.size(), m = grid1[0].size();
        this->n = n;
        this->m = m;
        UF uf(n*m);
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid1[i][j]) {
                    dfs(i, j, grid1, uf);
                } 
            }
        }
        int ret = 0;
         for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid2[i][j]) {
                    int root = uf.findSet(i*m + j);
                    ret += dfs2(i, j, grid2, uf,root) && grid[i][j];
                }
            }
        }
        return ret;
    }
};

using purely DFS

We can also solve it by using purely DFS, the checking is pretty simple:

For each element of the island from grid2, we check whether the corresponding element in grid1 is 1, if all of them is 1, then it is a sub island, if not, then it is not a sub island.

You can understand this by building some examples. Then the problem can be solved by using simple DFS or BFS.

vector<pair<int, int>> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
class Solution {
public:
    int n , m;
    vector<vector<int>> grid1;
     bool dfs(int i, int j, vector<vector<int>>& grid2){
        bool good = true;
        grid2[i][j] = 0;
        if (grid1[i][j] == 0) good = false;
        int r = 0, c = 0;
        for (auto [di, dj] : dirs){
            r = i + di, c = j + dj;
            if (r < 0 || r >= n || c < 0 || c >= m || grid2[r][c] == 0) continue;
            bool thisgood = dfs(r, c, grid2);
            if (!thisgood) good = false;
        }
         return good;
     }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        this->grid1 = grid1;
        const int n = grid1.size(), m = grid1[0].size();
        this->n = n;
        this->m = m;
        int ret = 0;
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid2[i][j]) {
                    auto thisret = dfs(i, j, grid2);
                    ret += thisret;
                }
            }
        }
        return ret;
    }
};

using purely BFS

We can also use BFS.

vector<pair<int, int>> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
class Solution {
public:
    int n , m;
    vector<vector<int>> grid1;
     bool bfs(int i, int j, vector<vector<int>>& grid2){
        bool good = true;
         queue<pair<int, int>> Q;
         Q.emplace(i, j);
         grid2[i][j] = 0;
         while(!Q.empty()){
             auto [i, j] = Q.front();Q.pop();
             if (grid1[i][j] == 0) good = false;
             for (auto [di, dj]: dirs){
                 int r = i + di, c = j + dj;
                 if (r < 0 || r >= n || c < 0 || c >= m || grid2[r][c] == 0) continue;
                 Q.emplace(r, c);
                 grid2[r][c] = 0;
             } 
         }
          return good;
     }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        this->grid1 = grid1;
        const int n = grid1.size(), m = grid1[0].size();
        this->n = n;
        this->m = m;
        int ret = 0;
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid2[i][j]) {
                    auto thisret = bfs(i, j, grid2);
                    ret += thisret;
                }
            }
        }
        return ret;
    }
};