Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Find the total number of islands using DFS | FACE Prep

Published on 09 Mar 2020

Program to find the total number of islands using DFS is discussed here. Given an input island matrix, where 0 represents water and 1 represents land. Find the total number of islands that are formed by connected 1's.


For example, consider the input island matrix

1 0 1 0 1

0 0 1 0 0

0 0 1 1 0

0 1 0 1 0

1 1 1 0 0

0 0 0 0 1

0 1 0 1 0

0 0 1 1 0

0 0 0 1 1

1 1 0 0 0


Total number of islands = 5

total number of islands using dfs

´╗┐Algorithm to find the number of islands using DFS


  1. Input the island matrix.
  2. Traverse the entire matrix.
  3. Whenever you find 1 use DFS to find all the connected ones in the 8 direction.
  4. Change them to 0 to indicate that this element is traversed and increase the island count by 1.
  5. Return count.


Program to find the number of islands using DFS is given below.


C
C++

Output
Enter the order of the islands : 10 5
Enter the island matrix :
1 0 1 0 1
0 0 1 0 0
0 0 1 1 0
0 1 0 1 0
1 1 1 0 0
0 0 0 0 1
0 1 0 1 0
0 0 1 1 0
0 0 0 1 1
1 1 0 0 0

Total Number of islands : 5


Time complexity: O(n^2)


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in