Given a collection of n edges, each represented by three numbers a, b, and c, you need to: • Output whether we can even make a MST. This requires that our graph can have all nodes connected to one another without cycling and without creating disjoint graphs. • Output the magnitude of the MST, or in other words the value of all edges of the MST added together. If there is no MST possible, output "No". If there is, output "Yes" and continue to the second task. On a new line, output "MST = " + the magnitude of the MST. a is the label of one vertex, b is the label of the other vertex, and c is the size of the edge that connects them. Each value is separated by a space, and each line ends with a endl character. The input will begin with the value of n, followed by a number of combinations of a, b, and c that could be constructed (note: the number of lines are not necessarily equal to or less than n). Make sure your output follows the structure given in the test cases. You MAY use STL to construct the graph, using vectors, lists, maps, or however you want to create them. Additionally, the use of STL implementation of priority queues are highly encouraged. However, you must implement either Prim's or Krustal's algorithm by hand. Either algorithm can be used: it will not impact results. Pick your favorite! Case 1: Input 1: 6 Output 1: Yes 0 1 9 MST = 20 0 4 8 1 5 5 2 0 6 3 2 2 1 3 1 2 1 3 4 3 7 5 3 4 Case 2: Input 2: 7 Output 2: No 2 3 3 1 0 1 6 5 9 2 0 5 2 4 1 0 4 4 1 3 7 3 0 7 Case 3: Input 3: 10 Output 3 is unknown, solve. 0 1 19 (that means put your own solution 3 4 1 here,
c++
Given a collection of n edges, each represented by three numbers a, b, and c, you need to: • Output whether we can even make a MST. This requires that our graph can have all nodes connected to one another without cycling and without creating disjoint graphs. • Output the magnitude of the MST, or in other words the value of all edges of the MST added together. If there is no MST possible, output "No". If there is, output "Yes" and continue to the second task. On a new line, output "MST = " + the magnitude of the MST. a is the label of one vertex, b is the label of the other vertex, and c is the size of the edge that connects them. Each value is separated by a space, and each line ends with a endl character. The input will begin with the value of n, followed by a number of combinations of a, b, and c that could be constructed (note: the number of lines are not necessarily equal to or less than n). Make sure your output follows the structure given in the test cases. You MAY use STL to construct the graph, using
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
