Week 5 - Assignment 2 - CS103 - Swayam

Week 5 - Assignment 2

Problem Statement

You are teaching a class of n students. Each student may be friends with some other students or may have no friends. Students who are friends with each other sit adjacent to each other in the class. If a student a is friends with a student b, but not with a student c, but b is friends with c, then they still sit together as both a and c will sit adjacent to b, their mutual friend. All friendships are symmetric, meaning that if a is a friend of b, then b is a friend of a for all a, b ∈ Students.

You are trying to give the students a group project, but the students are adamant and will not agree to random grouping. You are thus left with no choice but to let them create groups with their friends. This may lead to unequal size groups.

You don't know which student is friends with which student, and asking the same from all n students will require a lot of time. Thus, you decide to simply look at how they are sitting and form groups that way.

A student a will be in the same project group with a student b if either a and b are friends, or a and c are friends and b and c are friends, for any arbitrary student c, such that c ≠ a and c ≠ b. Two students are friends with each other if they are sitting adjacent (horizontally or vertically, but not diagonally) to each other.

Given the sitting arrangement of the students in a rectangular classroom, output the number of groups they will form for the project.

Input Format

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

Each test case contains several lines of input:

Constraints

Output Format

For each test case, output a single integer x, which is the number of groups the students will form.

Sample Input

1
4 4
1 0 0 1
0 1 1 0
1 0 0 0
1 1 1 1

Sample Output

4

Explanation

In the classroom, there are 4 connected groups of students with sizes {1, 1, 2, 5} sitting together. Thus, they will form 4 groups for the group project.

Solution

def dfs(grid, visited, i, j, n, m):
    # Check if the current cell is out of bounds or has been visited already,
    # or if the cell is not a student (represented by 1 in the grid).
    if i < 0 or j < 0 or i >= n or j >= m or visited[i][j] or grid[i][j] == 0:
        return  # If any of these conditions are met, return and do not proceed further.
    
    # Mark the current cell as visited
    visited[i][j] = True
    
    # Recursively explore all four possible directions: up, down, left, right
    # Move up (row - 1)
    dfs(grid, visited, i - 1, j, n, m)
    # Move down (row + 1)
    dfs(grid, visited, i + 1, j, n, m)
    # Move left (column - 1)
    dfs(grid, visited, i, j - 1, n, m)
    # Move right (column + 1)
    dfs(grid, visited, i, j + 1, n, m)

def count_groups(grid, n, m):
    # Initialize a 2D list `visited` to keep track of which cells have been visited.
    # Initially, all cells are unvisited, so all values are set to False.
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    # Variable to keep count of the number of groups (connected components)
    group_count = 0
    
    # Iterate over every cell in the grid
    for i in range(n):
        for j in range(m):
            # If the current cell contains a student (1) and hasn't been visited yet,
            # it's the start of a new group.
            if grid[i][j] == 1 and not visited[i][j]:
                # Perform DFS to visit all connected cells (part of the same group)
                dfs(grid, visited, i, j, n, m)
                # Increment the group count after finishing the DFS, indicating one complete group has been found
                group_count += 1
    
    # Return the total number of groups found in the grid
    return group_count

# Reading input
t = int(input())  # Read the number of test cases
for _ in range(t):
    n, m = map(int, input().split())  # Read the dimensions of the grid (n: rows, m: columns)
    
    # Initialize the grid as an empty list
    grid = []
    
    # Read each row of the grid
    for _ in range(n):
        # Convert each input line to a list of integers and append it to the grid
        grid.append(list(map(int, input().split())))
    
    # Output the number of groups (connected components of students) for each test case
    print(count_groups(grid, n, m))

Sample Solution Provided by Instructor

def groups(grid):
    if not grid:
        return 0  # If the grid is empty, return 0 as there are no groups.

    # Helper function to perform DFS and mark visited cells.
    def dfs(i, j):
        # If the current cell is out of bounds or not a '1', return (stop recursion).
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != 1:
            return
        grid[i][j] = 0  # Mark the cell as visited by setting it to '0'.

        # Recursively visit all adjacent cells (up, down, left, right).
        dfs(i+1, j)  # Move down
        dfs(i-1, j)  # Move up
        dfs(i, j+1)  # Move right
        dfs(i, j-1)  # Move left

    ngroups = 0  # Initialize the group counter.

    # Iterate over all cells in the grid.
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:  # Found an unvisited '1', which is the start of a new group.
                ngroups += 1  # Increment the group counter.
                dfs(i, j)  # Perform DFS to visit the entire group.

    return ngroups  # Return the total number of groups found.

# Main logic to handle multiple test cases.
t = int(input())  # Read the number of test cases.
for _ in range(t):
    n, m = list(map(int, input().split()))  # Read the dimensions of the grid.
    grid = []
    for _ in range(n):
        grid.append(list(map(int, input().split())))  # Read the grid row by row.
    print(groups(grid))  # Print the number of groups for the current grid.