Week 4 - Assignment 2 - CS103 - Swayam

Week 4 - Assignment 2

1. Problem Description

Your family is planning a memorable trip to Thailand to visit its beautiful islands. These islands are part of different archipelagos, each with its unique beauty. The islands within an archipelago are connected by boat tours, allowing travel from one island to another within the same archipelago. However, there are no boat tours connecting islands in different archipelagos.

You are given the number of islands and the boat tours between them. Each island is numbered from 1 to the total number of islands. If a boat tour exists between island u and island v, it is assumed that a return boat trip also exists.

Your task is to determine how many separate archipelagos exist, given the information about the islands and the boat tours.

1.1 Input Format

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

For each test case:

1.2 Constraints

1.3 Output Format

For each test case, print a single integer denoting the number of separate archipelagos that exist in Thailand.

1.4 Sample Input

1
12 9
5 6
1 3
1 2
4 5
2 3
4 6
7 8
9 10
8 9

1.5 Sample Output

5

1.6 Explanation

In the given example, there are 12 islands. The boat tours connect some of these islands, forming several archipelagos:

Thus, there are a total of 5 archipelagos in this scenario.

Solution

# Depth First Search (DFS) function to explore the graph
def dfs(node, graph, visited):
    # Initialize a stack with the starting node
    stack = [node]
    
    # Continue the process as long as there are nodes in the stack
    while stack:
        # Pop the last node from the stack (LIFO order)
        current = stack.pop()
        
        # Explore all neighbors (connected nodes) of the current node
        for neighbor in graph[current]:
            # If the neighbor hasn't been visited yet
            if not visited[neighbor]:
                # Mark the neighbor as visited
                visited[neighbor] = True
                # Push the neighbor onto the stack to explore it later
                stack.append(neighbor)

# Function to count the number of disconnected components (archipelagos) in the graph
def count_archipelagos(islands, boat_tours):
    # Initialize the graph as a dictionary where each island is a key and its value is an empty list (its neighbors)
    graph = {i: [] for i in range(1, islands + 1)}
    
    # Initialize a dictionary to track visited islands; initially, all are unvisited (False)
    visited = {i: False for i in range(1, islands + 1)}
    
    # Build the graph based on the boat tours
    for u, v in boat_tours:
        # Since it's an undirected graph, add each island to the other's adjacency list
        graph[u].append(v)
        graph[v].append(u)
    
    # Initialize a counter for the number of archipelagos (disconnected components)
    archipelagos_count = 0
    
    # Iterate over each island to start DFS if the island hasn't been visited
    for island in range(1, islands + 1):
        # If the island hasn't been visited, it means it's the start of a new archipelago
        if not visited[island]:
            # Mark the island as visited
            visited[island] = True
            # Use DFS to visit all islands in this archipelago
            dfs(island, graph, visited)
            # After visiting all connected islands, increment the archipelago count
            archipelagos_count += 1
    
    # Return the total number of archipelagos found
    return archipelagos_count

# Main function to handle multiple test cases
def main():
    # Read the number of test cases
    t = int(input().strip())  
    # Initialize a list to store results of each test case
    results = []
    
    # Iterate over each test case
    for _ in range(t):
        # Read the number of islands and boat tours for this test case
        islands, tours = map(int, input().strip().split())
        # Read each boat tour as a tuple of two connected islands
        boat_tours = [tuple(map(int, input().strip().split())) for _ in range(tours)]
        # Count the number of archipelagos for this test case and store the result
        results.append(count_archipelagos(islands, boat_tours))
    
    # Print all results for each test case
    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

def make_set(parent, rank, n):
    # Initialize the parent and rank arrays for 'n' nodes.
    # Each node starts as its own parent (self-loop), and the rank is initially set to 0.
    for i in range(1, n + 1):
        parent[i] = i
        rank[i] = 0

def find_parent(node, parent):
    # This function finds the representative (root) of the set containing 'node'.
    # It uses path compression to make future queries faster by directly linking nodes to the root.
    if node == parent[node]:
        return node
    # Recursively find the root and compress the path by setting the parent of 'node' to the root.
    parent[node] = find_parent(parent[node], parent)
    return parent[node]

if __name__ == "__main__":
    t = int(input())  # Read the number of test cases.
    while t > 0:
        islands, boat_tours = map(int, input().split())  # Number of islands and boat tours.

        # Initialize parent and rank arrays for all islands.
        parent = [0] * (islands + 1)
        rank = [0] * (islands + 1)
        make_set(parent, rank, islands)  # Create the initial sets where each island is its own set.

        # Process each boat tour (connection between two islands).
        for _ in range(boat_tours):
            u, v = map(int, input().split())  # Read the two islands connected by this boat tour.

            # Find the representatives (roots) of the sets containing 'u' and 'v'.
            u = find_parent(u, parent)
            v = find_parent(v, parent)

            # Union by rank: attach the tree with the lower rank under the root of the higher rank tree.
            if rank[u] < rank[v]:
                parent[u] = v
            elif rank[v] < rank[u]:
                parent[v] = u
            else:
                # If ranks are equal, arbitrarily choose one as the root and increase its rank.
                parent[v] = u
                rank[u] += 1

        # Count the number of distinct sets (archipelagos) by checking how many nodes are their own parent.
        archipelagos = 0
        for i in range(1, islands + 1):
            if find_parent(i, parent) == i:
                archipelagos += 1

        print(archipelagos)  # Output the number of archipelagos.
        t -= 1  # Move to the next test case.