Number of Islands

Graphs · components · Start a traversal once per new component · Stretch · about 25 min

Why it matters

Connected components are one of the most useful graph ideas.

How it connects

Flood fill visited one region. Now count how many times you need to begin a new visit.

Try first

When should the island count increase?

Interview cue

Each DFS/BFS erases one whole component, so the outer scan counts components exactly once.