Minimum Spanning Tree Sum

Moderate

0/80

Average time to solve is 40m

Contributed by

1 upvote

Asked in company

Problem statement

You are given an undirected, weighted graph consisting of ‘N’ vertices and ‘M’ edges. Your task is to select 'N' - 1 edge such that a path exists between each pair of vertices and the weight of the spanning tree of the graph is minimum.

A minimum spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible sum of the weight of edges.

For Example :

Consider a graph having 4 vertices. These 4 vertices are connected by 5 bidirectional edges given as :
1 --- 2 with weight = 8
2 --- 3 with weight = 6
3 --- 4 with weight = 5
1 --- 4 with weight = 2
1 --- 3 with weight = 4

Now, the best way to choose 3 edges is:
2 --- 3 with weight = 6
1 --- 4 with weight = 2
1 --- 3 with weight = 4
The weight of the minimum spanning tree is 2 + 4 + 6, i.e., 12.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains an integer 'T' denoting the number of test cases. 

The first line of each test case or query contains two space-separated integers 'N' and ‘M’ representing the number of vertices and edges in the graph. 

The next 'N' lines of every test case contain three single space-separated integers ‘A’, ‘B’ and ‘C’, representing an edge between the vertices 'A' and 'B' and 'C' denoting the weight of the edge.

Output Format:

For each test case, print N - 1 line each containing 3 space-separated integers 'A', 'B', and 'C' representing the edge you have chosen and the weight to traverse that edge.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 10
1 <= 'N' <= 1000
N - 1 <= 'M' <= 2000
1 <= 'C' <= 10^6 

Time limit: 1 sec

Sample Input 1:

Sample Output 1 :

Explanation:

For test case 1:
Here 'N' = 3, So we need to pick 2 edges such that all vertices are visited, and weight is minimum. Now the possible ways are.
1. [(1, 2), (2, 3)] : In this case, the weight of the spanning tree is 2 + 3 = 5.
2. [(1, 2), (1, 3)] : In this case, the weight of the spanning tree is 2 + 4 = 6.
3. [(2, 3), (1, 3)] : In this case, the weight of the spanning tree is 4 + 3 = 7.

Clearly, the weight is minimal in the first case so we pick [(1, 2), (2, 3)] with the weight 5. 

For test case 2:
Here 'N' = 4, So we need to pick 3 edges such that all vertices are visited, and weight is minimum. Now the possible ways are.
1. [(1, 2), (2, 3), (3, 4)] : In this case, the weight of the spanning tree is 2 + 3 + 4 = 9.
2. [(1, 2), (2, 3), (4, 1)] : In this case, the weight of the spanning tree is 2 + 3 + 1 = 6.
3. [(1, 2), (2, 3), (2, 4)] : In this case, the weight of the spanning tree is 2 + 3 + 3 = 8.
4. [(1, 2), (4, 1), (3, 4)] : In this case, the weight of the spanning tree is 2 + 1 + 4 = 7.
5. [(1, 2), (1, 3), (3, 4)] : In this case, the weight of the spanning tree is 2 + 4 + 4 = 10.
6. [(1, 2), (2, 4), (3, 4)] : In this case, the weight of the spanning tree is 2 + 3 + 4 = 9.
7. [(1, 2), (4, 1), (1, 3)] : In this case, the weight of the spanning tree is 2 + 1 + 4 = 7.
8. [(1, 2), (1, 3), (2, 4)] : In this case, the weight of the spanning tree is 2 + 4 + 3 = 9.
  and so on. 

Clearly, the weight is minimal in the second case, so we pick [(1, 2), (2, 3), (4, 1)] with the weight 6.

Sample Input 2:

Sample Output 2 :

1 2 1
1 2 1
2 3 3

Approaches (1)

Approach 1

Using Adjacency List

Time Complexity

Space Complexity

(100% EXP penalty)

Minimum Spanning Tree Sum

Console