Explore
Placement Prep

Edit

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

## ﻿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