Connected Components and Grid Problems
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A graph can fall apart into separate groups, and a grid of land and water is a graph too. The same search solves both: start it at every unseen node and count how many starts you need.
Connected components
A connected component is a group of nodes in which every node can reach every other by some path, and which has no edge to nodes outside the group.
A network may be split into groups that have no link to each other. Each group is a component. To count them, start a search at every node that is not yet seen, and add one for each new start.
def count_components(n, graph): seen, count = set(), 0 for start in range(n): if start in seen: continue count += 1 seen.add(start) stack = [start] while stack: for nxt in graph[stack.pop()]: if nxt not in seen: seen.add(nxt) stack.append(nxt) return countExample 1 · Count components
from collections import defaultdict
n = 7edges = [(0, 1), (1, 2), (3, 4), (5, 3)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def count_components(n, graph): seen, count = set(), 0 for start in range(n): if start in seen: continue count += 1 seen.add(start) stack = [start] while stack: for nxt in graph[stack.pop()]: if nxt not in seen: seen.add(nxt) stack.append(nxt) return count
print(count_components(n, graph))3
What this code does
- Nodes 0, 1, 2 are one group, 3, 4, 5 another, and node 6 has no edges and stands alone.
- So the answer is 3.
Example 2 · Size of each component
from collections import defaultdict
n = 7edges = [(0, 1), (1, 2), (3, 4), (5, 3)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
seen = set()sizes = []for start in range(n): if start in seen: continue seen.add(start) stack, size = [start], 0 while stack: node = stack.pop() size += 1 for nxt in graph[node]: if nxt not in seen: seen.add(nxt) stack.append(nxt) sizes.append(size)print(sizes)[3, 3, 1]
What this code does
- Counting the nodes taken out of the stack gives the size of each group.
- A graph is connected exactly when the list has one entry.
Looping over range(n) also counts nodes with no edges as their own component. BFS or DFS both work, and the total time is O(n + m).
A grid is a graph
A grid graph treats each cell of a rows by columns table as a node, joined to the cells above, below, left and right. The edges are never stored; they come from direction steps.
Each cell of a grid is a node. Its neighbours are the cells above, below, left and right, when they are inside the grid. No adjacency list is needed: a list of four steps gives the neighbours.
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbours(r, c, rows, cols): for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: yield nr, ncExample 3 · Neighbours of a cell
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbours(r, c, rows, cols): for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: yield nr, nc
print(list(neighbours(0, 0, 3, 3)))print(len(list(neighbours(1, 1, 3, 3))))[(1, 0), (0, 1)] 4
What this code does
- A corner cell has only two neighbours in the grid, the others fall outside.
- A middle cell has four.
The bounds check comes first, so no index goes outside the grid. A negative index would not fail in Python, it would wrap round to the other side, so the check matters.
Number of islands
An island is a group of land cells joined by shared sides: up, down, left or right. Cells that touch only at a corner are different islands.
In a grid of 1 for land and 0 for water, an island is a group of land cells joined up, down, left or right. Scan every cell. At a land cell not yet seen, count one island and search to mark all of it.
islands = 0for r in range(rows): for c in range(cols): if grid[r][c] == "1" and (r, c) not in seen: islands += 1 explore(r, c) # marks the whole island as seenExample 4 · Count the islands
grid = ["11000", "11010", "00100", "00011"]DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbours(r, c, rows, cols): for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: yield nr, nc
def island_sizes(grid): rows, cols = len(grid), len(grid[0]) seen, sizes = set(), [] for r in range(rows): for c in range(cols): if grid[r][c] == "1" and (r, c) not in seen: seen.add((r, c)) stack, size = [(r, c)], 0 while stack: cr, cc = stack.pop() size += 1 for nr, nc in neighbours(cr, cc, rows, cols): if grid[nr][nc] == "1" and (nr, nc) not in seen: seen.add((nr, nc)) stack.append((nr, nc)) sizes.append(size) return sizes
print(len(island_sizes(grid)))4
What this code does
- The grid has a block of four land cells, two single cells and a pair, so four islands.
- The cells at (2, 2) and (3, 3) only touch at a corner, so they are not joined.
Example 5 · Largest island
grid = ["11000", "11010", "00100", "00011"]DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbours(r, c, rows, cols): for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: yield nr, nc
def island_sizes(grid): rows, cols = len(grid), len(grid[0]) seen, sizes = set(), [] for r in range(rows): for c in range(cols): if grid[r][c] == "1" and (r, c) not in seen: seen.add((r, c)) stack, size = [(r, c)], 0 while stack: cr, cc = stack.pop() size += 1 for nr, nc in neighbours(cr, cc, rows, cols): if grid[nr][nc] == "1" and (nr, nc) not in seen: seen.add((nr, nc)) stack.append((nr, nc)) sizes.append(size) return sizes
print(max(island_sizes(grid)))print(island_sizes(grid))4 [4, 1, 1, 2]
What this code does
- The same search also counts the cells of each island, so one pass gives both the number and the sizes.
- If a grid has no land,
maxfails on an empty list. Usemax(sizes, default=0)for that case.
Each cell is looked at a constant number of times, so the time is O(rows times cols).
Flood fill
Flood fill is the paint-bucket tool. Starting at one cell, change its colour and the colour of every connected cell that had the same old colour. Check that the new colour differs first, or the search never ends.
Example 6 · Flood fill an image
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbours(r, c, rows, cols): for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: yield nr, nc
def flood_fill(image, sr, sc, new): rows, cols = len(image), len(image[0]) old = image[sr][sc] if old == new: return image image[sr][sc] = new stack = [(sr, sc)] while stack: r, c = stack.pop() for nr, nc in neighbours(r, c, rows, cols): if image[nr][nc] == old: image[nr][nc] = new stack.append((nr, nc)) return image
image = [[1, 1, 0], [1, 0, 0], [1, 1, 1]]flood_fill(image, 0, 0, 7)for row in image: print(row)[7, 7, 0] [7, 0, 0] [7, 7, 7]
What this code does
- The cell (0, 0) holds 1. All 1s connected to it become 7, and the 0s are not touched.
- Changing the cell as soon as it is added to the stack works as the seen mark, so no extra set is needed.
Next step
Check your understanding
10 quick questions