Skip to content
Tutorials Center
My learning

Topics

Lesson 124 of 225 ยท Graphs

Connected Components and Flood Fill

Count connected components, solve the number-of-islands problem, flood fill an image and run multi-source BFS (rotting oranges), with Python code you can run.

Some graphs are one big piece. Many are not. A road map of an archipelago has one cluster of towns per island, a social network has groups of people who never interact, and a photo has regions of similar color. Each separate piece is a connected component: a set of vertices where you can get from any vertex to any other by following edges, and which has no edge leading out to a vertex outside the set.

Finding components is the most common thing you do with breadth-first or depth-first search, and it hides inside a surprising number of interview problems: counting islands in a grid, filling a region with a color, spreading rot through a box of oranges. In this lesson you learn one simple template and then reuse it four times.

What a component looks like

TEXT
  0 --- 1        3 --- 4        5        6
  |                                      / \
  2                                     7---8

  component A = {0, 1, 2}
  component B = {3, 4}
  component C = {5}          (a lone vertex is a component too)
  component D = {6, 7, 8}

Every vertex belongs to exactly one component. If you start a search at vertex 0, it visits 0, 1 and 2 and then runs out of unvisited neighbors. It can never reach 3, because no path exists. So one search visits exactly one component.

That gives the whole algorithm:

  1. Keep a visited set.
  2. Go through every vertex. If it is not visited yet, it must belong to a component we have not seen: count one, and run a search from it that marks everything reachable as visited.
  3. The number of times you started a search is the number of components.

This works for undirected graphs. In a directed graph, "reachable from here" is not symmetric, and the right idea is strongly connected components.

Counting components with DFS

Here is the template. The inner loop marks every vertex reachable from start. It uses an explicit stack instead of recursion so that a long chain of vertices cannot hit Python's recursion limit.

Python Count and list connected components

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that we mark a vertex as visited when we push it, not when we pop it. Otherwise the same vertex could be pushed several times before it is popped. The outer loop is O(V) and every edge is looked at a constant number of times from each end, so the total cost is O(V + E) time and O(V) extra space for visited and the stack.

The same function with a queue instead of a stack (BFS) finds the same components. For counting, the order of exploration does not matter, only that everything reachable gets marked.

Is there a path between two vertices?

Components answer a classic question cheaply. Two vertices are connected by some path if and only if they are in the same component. If you will ask this question many times, label every vertex with a component id once, and then each query is a single comparison.

Python Component ids answer connectivity queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Preprocessing costs O(V + E) once, and each query is O(1). If edges are added over time, relabeling after every change is too slow, and you want union-find instead.

Grids are graphs: number of islands

A grid is a graph in disguise. Every cell is a vertex, and two cells are joined if they are neighbors up, down, left or right. You never build the adjacency list; you just compute the (up to four) neighbors on the fly.

The classic problem: a grid has land (1) and water (0). An island is a group of land cells joined horizontally or vertically. Count the islands, and find the area of the biggest one.

TEXT
  1 1 0 0 0
  1 1 0 0 0        3 islands:
  0 0 1 0 0          area 4 (top left)
  0 0 0 1 1          area 1 (middle)
                     area 2 (bottom right)

The brute force idea would be to compare every pair of land cells and decide whether a chain of land cells links them. That is hopelessly slow. The component idea is to scan the grid once; whenever you find unvisited land, you have found a new island, so you count it and flood through it.

Python Number of islands and biggest area

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is O(R x C) time and space for an R by C grid: each cell is pushed at most once and has four neighbors to check. If the problem says diagonal neighbors count, just use eight directions.

If you may modify the input, you can skip the seen table by overwriting visited land with "0" (or another marker). That removes the O(R x C) table and leaves only the stack. Say out loud that you are changing the input, because interviewers care.

Flood fill

The paint bucket tool in an image editor is a component search. Click a pixel, and every pixel of the same color that is connected to it takes the new color. Same template, but instead of counting you recolor.

Python Flood fill an image

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here the new color itself serves as the visited marker, which is why the old == color check matters. Without it, filling a region with its own color would never mark anything as new, and the loop would run forever.

Multi-source BFS: rotting oranges

Now a twist. A box of oranges is a grid: 0 is empty, 1 is a fresh orange and 2 is a rotten one. Every minute, each fresh orange next to a rotten one becomes rotten. How many minutes until no fresh orange is left? If some orange can never rot, answer -1.

A search from each rotten orange separately would be wasteful, and it would also give the wrong answer, because the rot spreads from all rotten oranges at the same time. The trick is multi-source BFS: put all the starting cells in the queue at the beginning. BFS then explores in rings of equal distance from the nearest source, and each ring is one minute.

TEXT
 minute 0      minute 1      minute 2
 2 1 1         2 2 1         2 2 2
 1 1 0         2 1 0         2 2 0
 0 1 1         0 1 1         0 1 1

We process the queue one level at a time (all cells that rot in the same minute) so we can count minutes.

Python Rotting oranges with multi-source BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the last example: two rotten oranges at the ends, so the middle orange rots after one minute, not two. Starting from all sources at once is what makes that work. The complexity is again O(R x C), because every cell enters the queue at most once.

Multi-source BFS shows up whenever the question is "distance to the nearest X": the nearest gate for every room, the nearest 0 for every cell, the nearest fire for every person. Seed the queue with every X.

Common mistakes

  • Marking visited too late. Mark when you push (or enqueue), not when you pop, or cells get queued many times and large grids become slow.
  • Forgetting bounds checks. grid[-1] does not raise an error in Python, it silently wraps to the last row. Always write 0 <= ny < rows.
  • Mutable rows shared by multiplication. [[False] * cols] * rows makes every row the same list. Use a comprehension.
  • Deep recursion on big grids. A recursive flood fill on a 1,000 x 1,000 grid can nest a million calls deep. Use an explicit stack or a queue.
  • Counting levels wrongly in BFS. Take len(queue) before the inner loop, because the queue grows while you process it.

When to use components

Use the template when the question is about groups: how many, how big, are these two together, which group is largest. If connections arrive one at a time and you must answer after each one, use union-find. If you need actual shortest routes, see breadth-first search and Dijkstra's algorithm.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A graph has 10 vertices and no edges at all. How many connected components does it have?

    Every vertex on its own is a component, so there are 10. The count never depends on whether you use BFS or DFS.
  2. 2. What is the time complexity of counting components of a graph stored as an adjacency list?

    Each vertex starts or joins one search, and each edge is examined a constant number of times, so the total is O(V + E).
  3. 3. In the number-of-islands problem on an R by C grid, how many times can a single cell be pushed on the stack if you mark cells when pushing?

    Marking at push time means a cell that is already marked is never pushed again, so each cell is pushed at most once and the work is O(R x C).
  4. 4. Why does rotting oranges start BFS with every rotten orange already in the queue?

    Seeding all sources makes BFS expand outward from the nearest rotten orange for every cell at once, so each queue level is exactly one minute.
  5. 5. What happens in flood fill if the new color equals the color of the starting cell and you skip the check?

    Recoloring is used as the visited marker. If the new color equals the old one, cells never become distinguishable from unvisited ones and get pushed again and again.

Summary

  • A connected component is a maximal set of vertices that can all reach each other; each vertex belongs to exactly one.
  • Count components by looping over all vertices and starting a DFS or BFS from every unvisited one. Cost: O(V + E).
  • Labeling vertices with component ids makes "are a and b connected?" an O(1) comparison.
  • A grid is an implicit graph: compute the four (or eight) neighbors on the fly and always check bounds. Islands and flood fill cost O(R x C).
  • Mark cells visited when you push them, and watch for the "new color equals old color" trap in flood fill.
  • Multi-source BFS starts with all sources in the queue and handles "distance to the nearest X" problems; process the queue level by level to count steps.

Next: Cycle Detection