Week 4 - Assignment 1 - CS103 - Swayam

Week 4 - Assignment 1

Problem Statement

In the year 2020, the COVID-19 pandemic posed a severe challenge globally, including in India. As the virus spread across various cities, public health officials and authorities faced the critical task of managing and containing the outbreak. To effectively allocate resources and implement quarantine measures, they needed to analyze the extent of infection spread within each city.

Imagine you are a public health official tasked with managing the COVID-19 pandemic in Mumbai. You have received a 2D map of the city, but the data collection was not done systematically, so instead of total counts of infected cases in each area, the map includes information on COVID-19 infections in the following format:

Your task is to identify neighbourhoods with the highest COVID-19 virus, where a neighbourhood denotes a cluster of people with an active COVID-19 virus and the connection between these people on the map is either horizontal or vertical.

Identify the neighbourhood with the highest COVID-19 virus and return the population of that neighbourhood.

Input Format

The first line of input contains one integer t, which is the number of test cases.

Each test case has the following input:

Constraints

Output Format

For each test case, print a single integer, denoting the population of the largest neighbourhood.

Sample Input

2
4 5
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Sample Output

9
4

Explanation

Solution

from collections import deque

# Breadth First Search (BFS) function to explore the grid
def bfs(grid, i, j, visited):
    # Initialize a queue with the starting position (i, j)
    queue = deque([(i, j)])
    
    # Mark the starting cell as visited
    visited[i][j] = True
    
    # Initialize the count of cells in the current connected component (neighbourhood)
    count = 1
    
    # Define possible directions for movement: right, left, down, up
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Continue exploring until the queue is empty
    while queue:
        # Pop the front element from the queue (FIFO order)
        x, y = queue.popleft()
        
        # Explore all four possible directions from the current cell
        for dx, dy in directions:
            # Calculate the new coordinates
            nx, ny = x + dx, y + dy
            
            # Check if the new position is within the grid bounds,
            # if it has not been visited, and if it is part of the neighborhood ('1')
            if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and not visited[nx][ny] and grid[nx][ny] == '1':
                # Add the new position to the queue for further exploration
                queue.append((nx, ny))
                # Mark this new position as visited
                visited[nx][ny] = True
                # Increment the count of connected cells
                count += 1
    
    # Return the total count of cells in this connected component
    return count

# Function to find the largest neighborhood in the grid
def largest_neighbourhood(grid):
    # Initialize a variable to store the maximum population found
    max_population = 0
    
    # Create a 2D list to track visited cells, initialized to False
    visited = [[False] * len(grid[0]) for _ in range(len(grid))]
    
    # Iterate over every cell in the grid
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            # If the cell is part of a neighborhood ('1') and hasn't been visited
            if grid[i][j] == '1' and not visited[i][j]:
                # Use BFS to find the size of this neighborhood
                max_population = max(max_population, bfs(grid, i, j, visited))
    
    # Return the size of the largest neighborhood found
    return max_population

# Main function to handle multiple test cases
def main():
    t = int(input().strip())  # Read the number of test cases
    results = []
    
    # Process each test case
    for _ in range(t):
        # Read the dimensions of the grid
        rows, cols = map(int, input().strip().split())
        grid = []
        
        # Read the grid rows
        for _ in range(rows):
            # Each row is read as a list of strings ('1' or '0')
            grid.append(input().strip().split())
        
        # Find the largest neighborhood for this grid and store the result
        result = largest_neighbourhood(grid)
        results.append(result)
    
    # Output the results for all test cases
    for result in results:
        print(result)

# Standard Python boilerplate to ensure the main function runs when the script is executed
if __name__ == "__main__":
    main()

Sample Solution Provided by Instructor

from collections import defaultdict

# Disjoint Set Union (DSU) or Union-Find class
class DSU:
    def __init__(self, n):
        # Initialize parent array where each element is its own parent (self-loop)
        self.parent = [i for i in range(n)]
        # Initialize rank array to keep track of the depth of trees
        self.rank = [0] * n

    # Find the representative of the set containing 'x' with path compression
    def find(self, x):
        # If 'x' is not its own parent, recursively find its parent and perform path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    # Union by rank - combine two sets containing 'x' and 'y'
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        # Only union if 'x' and 'y' are in different sets
        if rootX != rootY:
            # Union by rank: attach smaller tree under the root of the larger tree
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                # If ranks are equal, arbitrarily make one the root and increase its rank
                self.parent[rootX] = rootY
                self.rank[rootY] += 1

if __name__ == '__main__':
    t = int(input())  # Number of test cases

    for tt in range(t):
        m, n = map(int, input().split())  # Dimensions of the grid
        covid_map = []
        for i in range(m):
            covid_map.append(list(map(int, input().split())))  # Read the grid map

        # Initialize DSU with 'm * n' elements (one for each cell in the grid)
        dsu = DSU(m * n)

        # Helper function to convert 2D grid coordinates to 1D DSU index
        def index(i, j):
            return i * n + j

        # Iterate over the grid to union adjacent infected cells (i.e., with value 1)
        for i in range(m):
            for j in range(n):
                if covid_map[i][j] == 1:
                    # Union with the cell above it if it's also infected
                    if i > 0 and covid_map[i - 1][j] == 1:
                        dsu.union(index(i, j), index(i - 1, j))
                    # Union with the cell to the left if it's also infected
                    if j > 0 and covid_map[i][j - 1] == 1:
                        dsu.union(index(i, j), index(i, j - 1))

        # Use a dictionary to count the size of each connected component
        neighbourhood = defaultdict(int)
        for i in range(m):
            for j in range(n):
                if covid_map[i][j] == 1:
                    # Find the root of the current infected cell and count it in the neighbourhood
                    neighbourhood[dsu.find(index(i, j))] += 1

        # Determine the size of the largest connected component
        highest_population = max(neighbourhood.values(), default=0)
        print(highest_population)