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:
- The first line contains two space-separated integers islands and boat_tours, denoting the number of islands and the number of boat tours respectively.
- The next boat_tours lines each contain two integers u and v, indicating that a boat tour exists between island u and island v.
1.2 Constraints
- 1 ≤ t ≤ 100
- 1 ≤ islands ≤ 500
- 1 ≤ boat_tours ≤ islands × (islands − 1) / 2
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:
- Islands 1, 2, and 3 form one archipelago.
- Islands 4, 5, and 6 form another archipelago.
- Islands 7, 8, 9, and 10 form a third archipelago.
- Island 11 does not have any boat tours connecting it to other islands, making it an isolated archipelago.
- Island 12 is also isolated, forming its own archipelago.
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.