Connected Components

[!NOTE] If the world is a graph, continents are connected components. Your job is to count them.

1. The Problem: Counting Islands

Given a grid of 1s (Land) and 0s (Water), count the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

• Input: A Grid or Adjacency List.
• Output: An Integer (Count).
• Method: Iterate through every node. If it’s unvisited land, increment count and trigger a traversal (DFS/BFS) to mark the entire island as visited.

---

2. Interactive: Island Finder

Click to toggle Land/Water. The algorithm automatically counts the islands and colors them distinctly.

Islands Found: 0

---

3. Code Implementation: Number of Islands

Java

public int numIslands(char[][] grid) {
  if (grid == null || grid.length == 0) return 0;

  int count = 0;
  int rows = grid.length;
  int cols = grid[0].length;

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (grid[i][j] == '1') {
        count++;
        dfs(grid, i, j);
      }
    }
  }
  return count;
}

private void dfs(char[][] grid, int r, int c) {
  int rows = grid.length;
  int cols = grid[0].length;

  if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
    return;
  }

  grid[r][c] = '0'; // Mark as visited (sink the island)

  dfs(grid, r + 1, c);
  dfs(grid, r - 1, c);
  dfs(grid, r, c + 1);
  dfs(grid, r, c - 1);
}

Go

func NumIslands(grid [][]byte) int {
  if len(grid) == 0 {
    return 0
  }

  count := 0
  rows := len(grid)
  cols := len(grid[0])

  for r := 0; r < rows; r++ {
    for c := 0; c < cols; c++ {
      if grid[r][c] == '1' {
        count++
        dfs(grid, r, c)
      }
    }
  }
  return count
}

func dfs(grid [][]byte, r, c int) {
  if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == '0' {
    return
  }

  grid[r][c] = '0' // Sink

  dfs(grid, r+1, c)
  dfs(grid, r-1, c)
  dfs(grid, r, c+1)
  dfs(grid, r, c-1)
}

---

4. Deep Dive Strategy Lab: Connected Components

Intuition Through Analogy

Think of this chapter like city route planning. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?