Connected Components and Flood Fill

"How many separate friend groups are in this network? How many islands in this map? Both are the same question — how many disconnected pieces — and one BFS-or-DFS-from-each-unvisited-node answers it."

Connected Components

A connected component is a maximal group of nodes that can all reach each other. A social graph might be one big component plus a few isolated clusters; a map might have a mainland and several islands. Finding them is a clean pattern: loop over all nodes; each time you hit an unvisited one, launch a BFS or DFS from it. That single traversal floods through everything reachable — one whole component — marking them visited. The number of times you have to launch a fresh traversal is exactly the number of components. O(V + E) total, because each node and edge is touched once across all the traversals combined.

Flood Fill: the Same Idea on a Grid

A 2D grid is secretly a graph — each cell is a node, and its neighbors are the adjacent cells (up/down/left/right). So the paint-bucket tool, "count the islands," and region detection in an image are all flood fill: start at a cell and BFS/DFS to every connected same-colored cell, painting as you go. "Number of islands" is literally "count the connected components of land cells" — the exact same loop-and-flood pattern, just with grid coordinates as the nodes and implicit edges to the four neighbors. Recognizing a grid as a graph is one of the highest-leverage reframings in this whole track.

Connected components = launch a BFS/DFS from each still-unvisited node; the launch count is the component count, O(V+E) total. A grid IS a graph (cells = nodes, adjacency = edges), so flood fill / counting islands is the same loop-and-flood pattern.

A Cousin: Bipartite Check (2-Coloring)

The same traversal scaffold answers another classic: is a graph bipartite — can you split its nodes into two groups so every edge crosses between groups (no edge within a group)? Run BFS/DFS and try to 2-color the nodes, alternating colors across each edge; if you're ever forced to give two already-adjacent nodes the same color, it's not bipartite. This models 'can these be split into two teams with no internal conflict?' — scheduling, matching, conflict detection. It's a reminder that BFS/DFS isn't one algorithm but a scaffold you hang different bookkeeping on.

Pippa's Confession

"Count the islands" stumped me until Dad asked, "What if each grid cell were a graph node?" The whole problem dissolved — it was just connected components with the neighbors being the four adjacent cells. I'd been staring at it as a grid problem when it was a graph problem wearing grid coordinates. Ever since, when I see a grid, I quietly ask whether treating cells as nodes turns a hard-looking puzzle into a BFS I already know.

Code

Connected components and island flood fill·python

# COUNT CONNECTED COMPONENTS: one DFS launch per component.
def count_components(graph):
    visited, count = set(), 0
    def dfs(node):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                dfs(nb)
    for node in graph:
        if node not in visited:
            count += 1            # a fresh launch = a new component
            dfs(node)
    return count

g = {"A":["B"], "B":["A"], "C":["D"], "D":["C"], "E":[]}
print("components:", count_components(g))   # 3  ({A,B}, {C,D}, {E})

# NUMBER OF ISLANDS: a grid is a graph; flood-fill each land region.
def num_islands(grid):
    if not grid: return 0
    rows, cols, count = len(grid), len(grid[0]), 0
    def flood(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
            return
        grid[r][c] = "0"          # 'sink' it so we don't revisit (visited mark)
        flood(r+1, c); flood(r-1, c); flood(r, c+1); flood(r, c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1        # a new land cell = a new island
                flood(r, c)
    return count

ocean = [["1","1","0","0"], ["1","0","0","1"], ["0","0","1","1"]]
print("islands:", num_islands(ocean))   # 2

Exercise

Given a grid where 1 = land and 0 = water, with land cells connected only up/down/left/right (not diagonally), describe how flood fill counts the islands and what plays the role of the 'visited' set. Then: if diagonal connections also counted as adjacency, how would the answer change, and what single part of the code would you edit?

Hint

Loop every cell; on an unvisited land cell, increment the count and flood-fill (DFS/BFS) the whole connected region, sinking cells to 0 to mark them visited. Diagonal adjacency means adding the four diagonal neighbors to the flood's recursive calls — fewer, larger islands result.