Lesson 22.2 · Depth-First Search
Components and Flood Fill
Loop over every node; each time you find an unvisited one, start a DFS that marks its whole component. The number of starts is the number of components.
12 min
Think of it like this
Counting islands from a plane: when you spot land you haven't counted, you add one and paint the whole island so you never count it again.
1.Count by sinking
On a grid, the DFS from a land cell turns every connected land cell into water (or marks it visited). The outer loop continues; the next untouched land cell must belong to a new island.
The same DFS can return a value: the size of the region (max area of island) or whether it touches the border (enclaves, surrounded regions).
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]Step 1/4Scan from the top-left. (0,0) is unvisited land: count = 1, start DFS.
Remember
- Outer loop + DFS per new component.
- DFS can return region size or other facts.
- Grids: 4 directions unless told otherwise.
Common mistakes
- Connecting diagonal cells when the problem says up/down/left/right.