Skip to content
CodeItRaw
Graphs

Lesson 3/4

A graph does not have to be in one piece. Each group of nodes joined to one another is a component; on a grid these are islands. To count them you go through every cell in turn: when you meet a land cell not seen yet, you have found a new island; you start a walk there and mark the whole of it.

islands = 0
seen = set()
for r in range(len(grid)):
    for c in range(len(grid[0])):
        if grid[r][c] == "." and (r, c) not in seen:
            islands += 1
            reachable(grid, r, c, seen)
return islands
The two outer loops look for a starting point; the walk paints the island. The counter goes up only when a new walk starts, not inside the walk.

If you want the island's size you count the cells the walk paints: the difference in the set's size before and after, or a number the walk returns. For all the nested loops, the total work is the number of cells, because each cell is painted only once.

Tasks

Tasks open in order. Solve them all and the next lesson opens.

This lesson's tasks open when the lessons before it are finished. You can read the explanation now.

  1. 01

    Islands

    Function

  2. 02

    The Largest Island

    Function

  3. 03

    Visited as a List

    Code reading · Read the Big-O

If you would rather not wait for the order, every problem is open without locks: Problem list