Count the number of islands

Given a binary 2D matrix, containing the combination of 1’s and 0’s, where 0’s represents the water and 1’s represents the land. Our task is to find the count of the total number of connected islands. An island is a group of connected land (elements having value 1) and any of the 8 directions.

Example - 

Input-> Graph[5][4] = {{0, 1, 1, 0}
                       {0, 0, 1, 0}
                       {1, 0 ,1, 1}
                       {0, 0, 0, 0}
                       {1, 1, 0, 1}}

Output-> Total number of islands are 4.
The resulting islands are highlighted using colors.
{{0, 1, 1, 0}
{0, 0, 1, 0}
{1, 0, 1, 1}
{0, 0, 0, 0}
{1, 1, 0, 1}}

This problem is similar to finding the total number of connected components in a given graph.

Connected Components – Connected components in an undirected graph is a subgraphs in which any two vertices are connected to each other by a path. A complete graph has 1 connected component.

To find the number of connected components in a graph, we can use either DFS or BFS. Here we will solve the above problem of finding the count of the total number of islands using DFS.

Start from the first island, mark it visited, then visit all of its neighboring elements(in any of the 8 directions). While visiting the neighboring lands(elements with value 1) mark them visited by setting the value of the visited matrix to 1. Repeat this until not every element is visited.

Implementation

/*CPP code to count the
total nubmer of island */

#include <bits/stdc++.h>
using namespace std;

#define row 5 
#define col 4 


//recursively visited the neighbouring connected of current island
int dfs(int graph[][col], int i, int j, int n, int m, vector<vector<int> >&visited)
{
    if(i>=n || i<0 || j>=m || j<0)
        return -1;
    
    //check if current island is already     
    if(visited[i][j] == 1)
     return 0;
     
    /* if current elemnt is 0,
    mark is already visited*/
    if(graph[i][j] == 0){
        visited[i][j] = 1;
        return 0;
    }
    
    /* mark the element at the
    position i & j as visited */
    visited[i][j] = 1;
    int a[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    int b[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    
    
    //call the dfs on the 8 neighbouring elements
    for(int k=0; k<9; k++)
            dfs(graph, i+a[k], j+b[k], n, m, visited);
    
    return 0;
}

int findIslands(int graph[][col], int n, int m) 
{
    vector<vector<int> >visited(n, vector<int>(m,0));

    //variable res stores total 
    //number of connected island
    int res = 0;
    
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(visited[i][j] == 0 && graph[i][j] == 1)
            {
                /* If current element is not visited 
                than this is a sepeate island, visita
                all the neighbouring island and
                increase the total island count by 1*/
                dfs(graph, i, j, n, m, visited);
                res++;
            }
            
    return res;
}

//Driver Code
int main() 
{
    int graph[row][col] = {{0, 1, 1, 0}, 
                           {0, 0, 1, 0}, 
                           {1, 0 ,1, 1}, 
                           {0, 0, 0, 0}, 
                           {1, 1, 0, 1}};

    cout<<"Total Number of islands are "<<findIslands(graph, row, col)<<endl;
    
    return 0;
}

Output
Total Number of islands are 4

Time Complexity

The run-time complexity of the above program is O(N²).