Count Connected Building Communities in a Grid

Problem: Count Independent Communities (Connected Components) in a City Grid You are given a city map grid, an m x n 2D grid. grid[r][c] = 1 means there is a building grid[r][c] = 0 means empty land Two buildings belong to the same community if they are adjacent in the 4-directional sense (up/down/left/right). Each community corresponds to a connected component. Return the number of independent communities in the grid. Input/Output Input: m, n followed by m rows of n integers (0/1) Output: a single integer: the number of connected components of 1s Constraints (suggested) 1 <= m, n <= 2000 4-directional adjacency only (no diagonals) Examples 3 3 1 1 0 0 1 0 1 0 1 Output: 3 2 2 0 0 0 0 Output: 0 1 5 1 1 1 1 1 Output: 1 4 4 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 Output: 4 3 4 1 0 0 1 1 0 1 1 0 0 0 0 Output: 2 Follow-up (very large grid) If m, n are extremely large (cannot fit in memory at once, or stored on disk), explain how you would handle/optimize (e.g., tiling/chunking, external-memory processing, parallelization, or union-find approaches). Example Input 3 3 1 1 0 0 1 0 1 0 1 Output 3