Connected Groups (BFS)

Problem Count connected groups in a grid/graph — Number-of-Islands-shaped, but expect twists in the test set (diagonal adjacency, wrap-around, values beyond 0/1, or huge sparse inputs).

Input / Output

• Input: grid (or adjacency data). Output: component count.

Constraints

• Up to 10^3 x 10^3 grid; O(cells) expected; recursion depth can overflow on snake-shaped components — prefer iterative BFS or an explicit stack.

Example

• [[1,1,0],[0,1,0],[0,0,1]] → 2 with 4-adjacency; 1 with 8-adjacency — confirming adjacency is the first clarifying question.

Expected approach

• Flood fill: scan cells; on unvisited land, count++ and BFS/DFS-mark the component. O(mn)/O(mn). Union-Find alternative for incremental/streaming variants. The "caveats" to defensively probe: adjacency definition, multiple land values (group by equal value?), borders/wrap, empty grid, single row/column, and stack depth — enumerate edge tests aloud before submitting.