Connecting Cities With Minimum Cost

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
16 upvotes
Asked in companies
MicrosoftSquadstackAmazon

Problem statement

There are ‘N’ cities numbered from 1 to ‘N’ and ‘M’ roads. Each road connectss two different cities and described as a two-way road using three integers (‘U’, ‘V’, ‘W’) which represents the cost ‘W’ to connect city ‘U’ and city ‘V’ together.

Now, you are supposed to find the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ denoting the number of cities and roads respectively.

Each of the next ‘M’ lines contains three single space-separated integers ‘U’, ‘V’, and ‘W’ denoting a two-way road between city ‘U’ and ‘V’ of cost ‘W’.
Output Format : 
For each test case, return an integer denoting the minimum cost.
Note : 
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^4
1 <= M <= 10^4
1 <= W <= 10^3
1 <= U, V <= N

Time Limit: 1 sec
Sample Input 1 :
2
5 6
1 2 6
2 3 5
3 4 4
1 4 1
1 3 2
3 5 3
3 1
1 2 4
Sample output 1 :
11
-1
Explanation of Sample output 1 :
For the first test case, the graph below describes the connection between the cities:

Example

We can choose the following roads to connect all the cities getting minimum cost:

Example

And its cost is 1 + 2 + 5 + 3 = 11

For the second test case, there is no way to connect all cities. So print -1.
Sample Input 2 :
2
3 3
1 2 1
2 3 2
3 1 3
4 3
1 2 4
2 3 5
3 4 1
Sample output 2 :
3
10
Explanation of Sample output 2 :
For the first test case, the minimum cost will be 3.

For the second test case, the minimum cost will be 10.
Hint

Can you think of a minimum spanning tree for this task?

Approaches (1)
Kruskal’s Minimum Spanning Tree Algorithm

The basic idea of this approach is to convert this task into a graph problem. Consider an undirected weighted graph of cities as nodes and roads as edges. Now, we need to find the minimum cost to connect all the cities which is equivalent to finding the minimum spanning tree of the graph.

 

We can use Kruskal’s Minimum Spanning Tree Algorithm for this task.

 

Please refer to https://cp-algorithms.com/graph/mst_kruskal.html for a detailed explanation of Kruskal’s Algorithm.

 

The basic idea of Kruskal’s algorithm is to sort the edges of the graph in non-decreasing order by its weight. And place all the nodes of the original graph isolated from each other, to form a forest of single node trees. Then, at each step of the algorithm, we will try to merge the trees by an edge of the original graph. The idea here is to choose the edges greedily. At each iteration, choose the edge with the minimum weight which is not chosen previously. 

While choosing the edge, we will make sure that it doesn’t belong to the same subtrees (because adding that edge will create a cycle).
 

Let us visualize the algorithm for the first test case of sample test case 1.


 

The idea here is to use a Disjoint Set Union data structure to solve this task. You can refer to this article from cp-algorithms to read more about DSU. https://cp-algorithms.com/data_structures/disjoint_set_union.html
 

Since at each step of merging of two subtrees, we need to check if two vertices belong to the same subtrees or not. We can use the FIND_SET() function from DSU to do this task. Then, for performing the merge operation of two subtrees, we can use DSU UNION_SETS(). We will use the union by rank and path compression for optimization. 

 

Now consider the following steps for implementing the algorithm:

  1. Create a DSU structure and initialize it using MAKE_SET() for each vertex of the graph. MAKE_SET() function will create a new set for each node of the graph which means every node will form a subtree. The node itself will be the parent of its respective set. Also, create variable “cost” and initialize it to zero which stores the weight of the minimum spanning tree.
  2. Sort the array/list of edges in ascending order by their weight.
  3. Now start iterating the array/list of edges.
    • Check if both vertices of the current edge (u, v) belong to different subtrees or not. We can use the FIND_SET() function which finds and returns the representative(also called parent) of a set that contains the provided element. The parent is one of the elements of the set. Since we need to check if ‘u’ and ‘v’ belong to the same subtree (here the same set) we can simply check if the parent of their sets are the same or not. If ( FIND_SET(u) != FIND_SET(v ) then,
      • Add the weight of the current edge to “cost”.
      • Merge two subtrees(sets). Here we can use UNION_SETS(u, v) function which merges the two specified sets (the set in which the first element is located, and the set in which the second element is located).
  4. Now we will iterate through each node (cities) and check if they belong to the same connected component or not.
    • Store the parent of node 1 in a variable “PARENT_OF_ALL”.
    • Now, iterate through all nodes from 2 to ‘N’ and check if the parent of the current node is “PARENT_OF_ALL”. If not, then return -1.
    • Since the parent of all nodes is the same so return the minimum cost.
Time Complexity

O(M * log(M) + N + M), where ‘N’ and ‘M’ denotes the number of nodes and edges in the graph, respectively.

 

Since we are sorting the array/list of edges, it will take O(M*log(M)) time. And then we are initializing the DSU which takes O(N) time. Along with that at each iteration of merging, we are using find_set() and union_sets() function of DSU which takes nearly O(1) time. So the overall time complexity will be O(M * log(M) + N + M).

Space Complexity

O(N + M), where ‘N’ and ‘M’ denotes the number of nodes and edges in the graph, respectively.

 

Since we are storing the array/list of edges, and also the DSU will take O(N) space.  So the overall space complexity will be O(N + M).

Code Solution
(100% EXP penalty)
Connecting Cities With Minimum Cost
Full screen
Console