Week 7 - Assignment 2 - CS103 - Swayam

Week 7 - Assignment 2

Problem Statement

On the occasion of Raksha Bandhan, you are tasked to deliver a lot of rakhis. Your company manufactures rakhis and sends out to customers. Your data analysts have found out the cities where your customers order rakhis from. However you don't have your own logistic branch to deliver all the rakhis, rather you use RedDart as the logistic provider. They only deliver from and to some select cities. Each inter-city delivery route has a cost associated with it.

You want to connect all of your destination cities with each other in such a way that the lowest amount of money is spent in shipping all the rakhis, yet all the cities are connected to each other, either directly, or indirectly.

Given the route RedDart ships to, find the minimum cost you would incur on the day of Raksha Bandhan.

Cost is defined as the amount incurred to your company to send one single rakhi across your network of all the cities. You can start from any of the cities.

Input Format

The first line of input is a single integer t denoting the number of test cases. t test cases follow.

The first line of each test case contains two space-separated integers n and m.

Next m lines follow, each with three space-separated integers x, y, and z denoting the ith route from city x to city y of cost z.

Constraints

Output Format

For every test case, output a single integer, which is the cost of sending one rakhi across the city network.

Example

Sample Input

1
5 6
1 2 3
2 3 4
3 4 4
4 5 3
5 1 2
1 3 2

Output:

10

Explanation

The given graph can be visualized as follows:

1 5 2 3 4 2 3 4 4 3 2

The lowest cost path to connect all the cities together is as follows:

1 5 2 3 4 2 3 3 2

The cost of this Minimum Spanning Tree (MST) is 10.

Solution

class UnionFind:
    def __init__(self, n):
        # Initialize the union-find structure with n elements.
        # 'parent' keeps track of the parent of each node, initially each node is its own parent.
        self.parent = list(range(n))
        # 'rank' keeps track of the tree depth to optimize union operations.
        self.rank = [1] * n

    def find(self, u):
        # This function finds the representative (root) of the set containing 'u'.
        # Path compression is used here to make future queries faster.
        if self.parent[u] != u:
            # Recursively find the root and make all nodes on the path point directly to the root.
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        # This function unites the sets containing 'u' and 'v'.
        root_u = self.find(u)
        root_v = self.find(v)
        # Only union if the roots are different, meaning they are in different sets.
        if root_u != root_v:
            # Union by rank: attach the smaller tree under the root of the larger tree.
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                # If both have the same rank, make one the root and increase its rank.
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
            return True
        return False

def kruskal(n, edges):
    # Function to perform Kruskal's algorithm to find the MST cost.
    uf = UnionFind(n)  # Initialize Union-Find for 'n' cities.
    # Sort all the edges by their weight in non-decreasing order.
    edges.sort(key=lambda x: x[2])
    mst_cost = 0  # Variable to store the total cost of the MST.
    
    # Iterate through the sorted edges and add them to the MST.
    for u, v, weight in edges:
        # Attempt to union the two nodes, if they are not already in the same set.
        if uf.union(u - 1, v - 1):
            mst_cost += weight  # If union was successful, add the weight of the edge to the total cost.
    
    return mst_cost  # Return the total cost of the MST.

# Read the number of test cases.
t = int(input())

# Process each test case.
for _ in range(t):
    # Read the number of cities 'n' and the number of routes 'm'.
    n, m = map(int, input().split())
    edges = []  # List to store all routes as edges.
    
    # Read all the routes.
    for _ in range(m):
        x, y, z = map(int, input().split())
        # Add the route as an edge to the list (x, y, z), where x and y are cities and z is the cost.
        edges.append((x, y, z))
    
    # Calculate the MST cost using Kruskal's algorithm.
    result = kruskal(n, edges)
    # Print the result for this test case.
    print(result)

Explanation

The given problem can be solved using Kruskal's algorithm to find the minimum spanning tree (MST) of the graph representing the cities and their shipping routes. The algorithm is implemented using the UnionFind class to perform union-find operations efficiently and the kruskal function to find the MST cost.

The UnionFind class is used to maintain the disjoint sets of cities and perform union and find operations efficiently. The kruskal function sorts the edges by weight and iterates through them, adding edges to the MST if they connect disjoint sets of cities.

The main function reads the input, processes each test case, and outputs the minimum cost of sending one rakhi across the city network for each test case.

Complexity Analysis

Let n be the number of cities and m be the number of routes between cities.

The time complexity of the solution is O(m log m) for sorting the edges and O(m α(n)) for performing union-find operations, where α(n) is the inverse Ackermann function, which grows very slowly and can be considered constant for practical purposes.

Therefore, the overall time complexity of the solution is O(t * (m log m + m α(n))) for t test cases.

The space complexity of the solution is O(n + m) to store the edges and the Union-Find data structure.

Sample Solution Provided by Instructor