Graph Traversal

Graph

Given a n*n grid of square; each square can be 1 (land) or 0 (water). An island is a maximally connected land square; two land square are connected if they have common edges.

Find the number of islands for the given grid of squares

Example 1

Input:
6
1 1 0 0 1 1
1 0 1 1 0 0
1 0 0 1 1 1
0 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
Output:
3
Explanation:
There are three connected land areas: top left, top right, and bottom.  

Example 2

Input:
10
1 1 1 0 0 0 0 0 1 1
0 1 0 0 1 1 1 1 0 0
1 1 1 1 0 1 1 0 0 1
1 0 0 1 0 1 1 1 1 1
1 0 1 0 1 1 0 1 0 1
1 1 0 0 0 0 0 0 0 1
0 0 1 0 1 1 1 0 0 1
0 1 1 1 1 0 1 0 1 1
1 0 1 1 1 1 1 0 1 0
0 1 1 0 0 0 0 1 0 0
Output:
7
Explanation: