Count Connected Regions

1. Background Knowledge

Connected component labeling (CCL) identifies distinct regions of connected pixels in binary images, crucial for image segmentation tasks like object counting and blob detection. In a binary grid, 1s represent foreground pixels and 0s represent background; regions are connected via 4-connectivity (horizontal/vertical adjacency, not diagonal).

Union-Find (Disjoint Set Union - DSU) is the key data structure: it efficiently manages sets of elements (pixels) and supports two operations:

• Find: Determine the representative (root) of a pixel's set.
• Union: Merge two sets when pixels are adjacent.

With path compression and union by rank, DSU achieves near-constant time per operation: $O($\alpha$(n))$ amortized, where $\alpha$ is the inverse Ackermann function (practically constant).

Prerequisites: 2D grid traversal, adjacency checks, and basic graph theory (pixels as nodes, edges between adjacent 1s).

2. Algorithm Approach

Use DSU for efficient CCL on grids:

• Assign each foreground pixel a unique initial label (or treat pixels as set elements).
• Scan the grid (raster order: row-by-row, left-to-right).
• For each 1, check its 4 neighbors (up/left, if exist and are 1).
• Union the current pixel with neighboring pixels' sets if they share the same foreground value.
• After scanning, count the number of distinct root parents among foreground pixels—this gives the connected region count.

This is a one-pass or two-pass variant adapted for DSU, avoiding traditional label resolution passes.

3. Step-by-Step Strategy

1. Initialize DSU:

• Map each pixel $(i,j)$ with grid[i][j] == 1 to a unique ID (e.g., id = i * cols + j).
• Each ID starts as its own parent; use rank array for union by rank.

2. Scan and Union:

for i in 0..rows-1:
for j in 0..cols-1:
if grid[i][j] == 1:
// Check left neighbor
if j > 0 and grid[i][j-1] == 1:
union(id(i,j), id(i,j-1))
// Check up neighbor
if i > 0 and grid[i-1][j] == 1:
union(id(i,j), id(i-1,j))

3. Count Roots:

• Use a set to collect unique find(id) for all foreground pixels.
• Return the set size.

Pseudocode:

class UnionFind:
 def __init__(self, size): self.parent = list(range(size)); self.rank = * size
 def find(self, x):
 if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])
 return self.parent[x]
 def union(self, x, y):
 px, py = self.find(x), self.find(y)
 if px != py:
 if self.rank[px] < self.rank[py]:
 self.parent[px] = py
 elif self.rank[px] > self.rank[py]:
 self.parent[py] = px
 else:
 self.parent[py] = px; self.rank[px] += 1

def count_regions(grid):
 if not grid or not grid: return 0
 rows, cols = len(grid), len(grid)
 uf = UnionFind(rows * cols)
 for i in range(rows):
 for j in range(cols):
 if grid[i][j] == 1:
 id1 = i * cols + j
 if j > 0 and grid[i][j-1] == 1: uf.union(id1, id1 - 1)
 if i > 0 and grid[i-1][j] == 1: uf.union(id1, (i-1) * cols + j)
 roots = set()
 for i in range(rows):
 for j in range(cols):
 if grid[i][j] == 1: roots.add(uf.find(i * cols + j))
 return len(roots)

4. Common Pitfalls

• Diagonal connectivity: Only check horizontal/vertical; ignore diagonals for 4-connectivity.
• Boundary checks: Always verify i>0, j>0 before accessing neighbors to avoid index errors.
• Isolated pixels: Single 1s form their own region—correctly counted as 1.
• All-background grid: Return 0; handle empty grids.
• Inefficient find without path compression: Leads to $O(n)$ worst-case; always implement it.
• Double-counting unions: Only union with left/up (not right/down) to avoid redundant operations during forward scan.

5. Time & Space Complexity

• Time: $O(rows \times cols \times$\alpha$(rows \times cols))$, where $\alpha \approx 4$ practically. Grid scan is $O(n)$ ($n = rows \times cols$); each union/find is amortized constant.
• Space: $O(rows \times cols)$ for DSU arrays (parent, rank) and root set.

This scales well for constraints ($n \leq 10,000$).