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; }

OutputTotal Number of islands are 4

#### Time Complexity

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